Title :
Parallel spatial joins using grid files
Author :
Kim, Jin-Deog ; Hong, Bong-Hee
Author_Institution :
Group Dept. of Info-Commun., Pusan Info-Tech Coll., South Korea
Abstract :
The most costly spatial operation in spatial databases is spatial join which combines objects from two data sets based on spatial predicates. Even if the execution time of sequential processing of a spatial join has been considerably improved, the response time is far from meeting the requirements of interactive users. In this paper, we have developed two kinds of parallel spatial join algorithms based on grid files: a parallel spatial join using a multi-assignment grid file and a parallel spatial join using a single-assignment grid file. We also present the cost of the two join algorithms in terms of the number of MBR comparisons. The experimental tests on the MIMD parallel machine with shared disks show that the first join algorithm based on disjoint decomposition of a data space outperforms the second based on non-disjoint decomposition
Keywords :
parallel algorithms; parallel databases; visual databases; MIMD parallel machine; data sets; disjoint decomposition; interactive users; multi-assignment grid file; nondisjoint decomposition; parallel spatial join algorithms; shared disks; single-assignment grid file; spatial databases; spatial predicates; Algorithm design and analysis; Analytical models; Costs; Delay; Educational institutions; Parallel machines; Parallel processing; Performance analysis; Spatial databases; Spatial indexes;
Conference_Titel :
Parallel and Distributed Systems, 2000. Proceedings. Seventh International Conference on
Conference_Location :
Iwate
Print_ISBN :
0-7695-0568-6
DOI :
10.1109/ICPADS.2000.857739