TY - GEN
T1 - A unified approach for indexed and non-indexed spatial joins
AU - Arge, Lars
AU - Procopiuc, Octavian
AU - Ramaswamy, Sridhar
AU - Suel, Torsten
AU - Vahrenhold, Jan
AU - Scott, Jeffrey Vitter
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.
PY - 2000
Y1 - 2000
N2 - Most spatial join algorithms either assume the existence of a spatial index structure that is traversed during the join process, or solve the problem by sorting, partitioning, or on-the-fly index construction. In this paper, we develop a simple plane-sweeping algorithm that unifies the index-based and non-index based approaches. This algorithm processes indexed as well as non-indexed inputs, extends naturally to multi-way joins, and can be built easily from a few standard operations. We present the results of a comparative study of the new algorithm with several index-based and non-index based spatial join algorithms. We consider a number of factors, including the relative performance of CPU and disk, the quality of the spatial indexes, and the sizes of the input relations. An important conclusion from our work is that using an index-based approach whenever indexes are available does not always lead to the best execution time, and hence we propose the use of a simple cost model to decide when to follow an index-based approach.
AB - Most spatial join algorithms either assume the existence of a spatial index structure that is traversed during the join process, or solve the problem by sorting, partitioning, or on-the-fly index construction. In this paper, we develop a simple plane-sweeping algorithm that unifies the index-based and non-index based approaches. This algorithm processes indexed as well as non-indexed inputs, extends naturally to multi-way joins, and can be built easily from a few standard operations. We present the results of a comparative study of the new algorithm with several index-based and non-index based spatial join algorithms. We consider a number of factors, including the relative performance of CPU and disk, the quality of the spatial indexes, and the sizes of the input relations. An important conclusion from our work is that using an index-based approach whenever indexes are available does not always lead to the best execution time, and hence we propose the use of a simple cost model to decide when to follow an index-based approach.
UR - http://www.scopus.com/inward/record.url?scp=84937438024&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84937438024&partnerID=8YFLogxK
U2 - 10.1007/3-540-46439-5_29
DO - 10.1007/3-540-46439-5_29
M3 - Conference contribution
AN - SCOPUS:84937438024
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 413
EP - 429
BT - Advances in Database Technology - EDBT 2000 - 7th International Conference on Extending Database Technology, Proceedings
A2 - Zaniolo, Carlo
A2 - Lockemann, Peter C.
A2 - Scholl, Marc H.
A2 - Grust, Torsten
PB - Springer Verlag
T2 - 7th International Conference on Extending Database Technology, EDBT 2000
Y2 - 27 March 2000 through 31 March 2000
ER -