Applying bulk insertion techniques for dynamic reverse nearest neighbor problems

Abstract

Reverse nearest neighbors queries have emerged as an important class of queries for spatial and other types of databases. The Rdnn-tree is an R-tree based structure that has been shown to perform outstandingly for such kind of queries. However, one practical problem facing it (as well as other type of indexes) is how to effectively construct the index from stretch. In this case, the cost of constructing and maintaining a Rdnn-Tree is about twice the cost of an R-Tree. Normal insertion into a Rdnn-Tree is performed one point at a time, known as single point insertion. The question arises, can insertion be improved there by reducing the construction and maintenance cost. In this paper we propose a bulk-loading technique, which is capable of significantly, improve the performance of constructing the index from stretch, as well as insert a large amount of data. Experiments show that our method outperforms the single point insertion significantly.