Efficient k-Closest-Pair Range-Queries in Spatial Databases

In order to efficiently retrieve the k closest pairs between two spatial data sets in a specified space, such as in GIS and CAD applications, we propose a novel algorithm to handle the k-closest-pair range-query problem by progressively augmenting the query window instead of finding all objects in the whole space. We first describe a specific range estimation method to compute the circle query range which helps eliminate the unnecessary distance calculations among spatial objects and improve performance. Then, we use R*-tree to store closest pairs and give algorithms for maintaining this structure. Extensive experiments performed with synthetic as well as with real data sets show that the new algorithm outperforms the existing approaches in most cases. In particular, this technique works well when two spatial data sets are identical.