Tie-breaking strategies for fast distance join processing
The distance join is a spatial join that finds pairs of closest objects in the order of distance by associating two spatial data sets. The distance join stores node pairs in a priority queue, from which node pairs are retrieved while traversing R-trees in top-down manners in the order of distance. This paper first shows that a priority strategy for the tied pairs in the priority queue during distance join processing greatly affects its performance. Then it proposes a probabilistic tie-breaking priority method. The experiments show that the proposed method is always better than alternative methods in the performance perspectives. (C) 2002 Published by Elsevier Science B.V.
distance join probabilistic tie-breaking priority distance distribution function