Incremental Distance Join Algorithms for Spatial Databases
Gísli R. Hjaltason (University of Maryland)
Hanan Samet (University of Maryland)
Two new spatial join operations, distance join and distance
semi-join, are introduced where the join output is ordered by the distance
between the spatial attribute values of the joined tuples. Incremental
algorithms are presented for computing these operations, which can be used
in a pipelined fashion, thereby obviating the need to wait for their
completion when only a few tuples are needed. The algorithms can be used
with a large class of hierarchical spatial data structures and arbitrary
spatial data types in any dimensions. In addition, any distance metric may
be employed. A performance study using R-trees shows that the incremental
algorithms outperform non-incremental approaches by an order of
magnitude if only a small part of the result is needed, while the penalty,
if any, for the incremental processing is modest if the entire join result
is required.