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.
Supported in part by National Science Foundation grants EIA-9870734 and EIA-9972879.
Supported in part by the U.S. Army Research Office under grant DAAH04-96-1-0013 and by the National Science Foundation under
grants CCR-9522047 and EIA-9870734.
This work was done while a Visiting Scholar at Duke University.