Title :
Graph partition based multi-way spatial joins
Author :
Lin, Xuemin ; Lu, Hai-Xin ; Zhang, Qing
Author_Institution :
Sch. of Comput. Sci. & Eng., New South Wales Univ., Sydney, NSW, Australia
Abstract :
We investigate the problem of efficiently computing a multi-way spatial join without spatial indexes. We propose a novel and effective filtering algorithm based on a two phase partitioning technique. To avoid missing hits due to an inherent difficulty in multi-way spatial joins, we propose to firstly partition a join graph into sub-graphs whenever necessary. In the second phase, we partition the spatial data sets; and then the sub-joins will be executed simultaneously in each partition to minimise the I/O costs. Finally, a multi-way relational join is applied to merge together the sub-join results. Our experiment results demonstrate the effectiveness and efficiency of the proposed algorithm.
Keywords :
graph theory; merging; query processing; relational databases; spatial data structures; visual databases; experiment results; filtering algorithm; graph partition; input output costs; join graph partitioning; merging; multi-way relational join; multi-way spatial joins; query processing; spatial data sets; spatial database; spatial indexes; two phase partitioning technique; Australia; Computer science; Costs; Filtering algorithms; Lakes; Partitioning algorithms; Query processing; Relational databases; Spatial databases; Spatial indexes;
Conference_Titel :
Database Engineering and Applications Symposium, 2002. Proceedings. International
Print_ISBN :
0-7695-1638-6
DOI :
10.1109/IDEAS.2002.1029653