An index structure for improving closest pairs and related join queries in spatial databases
Congjun Yang, King-Ip Lin · Proceedings - International Database Engineering and Applications Symposium · 2003
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.