Closest pair queries in spatial databases

This paper addresses the problem of finding the K closest pairs between two spatial data sets, where each set is stored in a structure belonging in th e R-tree family. Five different algorithms (four recursive and one iterativ e) are presented for solving this problem. The case of 1 closest pair is tr eated as a special case. An extensive study, based on experiments performed with synthetic as well as with real point data sets, is presented. A wide range of values for the basic parameters affecting the performance of the a lgorithms, especially the effect of overlap between the two data sets, is e xplored. Moreover, an algorithmic as well as an experimental comparison wit h existing incremental algorithms addressing the same problem is presented. In most settings, the new algorithms proposed clearly outperform the exist ing ones.