An index structure for improving closest pairs and related join queries in spatial databases

Abstract

Spatial databases have grown in importance in various fields. Together with them come various types of queries that need to be answered effectively. While queries involving a single data set have been studied extensively, join queries on multi-dimensional data like the k-closest pairs and the nearest neighbor joins have only recently received attention. In this paper we propose a new index structure, the b-Rdnn tree, to solve different join queries. The structure is similar to the Rdnn-tree for reverse nearest neighbor queries. Based on this new index structure, we give algorithms for various join queries in spatial databases. It is especially effective for k-closest pair queries, where earlier algorithms using the R*-tree can be very inefficient in many real life circumstances. To this end we present experimental results on k-closest pair queries to support the fact that our index structure is a better alternative.