Research Of Reverse Nearest Neighbor Query Based On Var~*-Tree

In the spatial database, the reverse nearest neighbor query is one of the most important queries, which is based on the nearest neighbor query. It is the focus and difficult of spatial database technology, how to the effective implementation of the reverse nearest neighbor queries have been a hot issue.The current study about RNN is not many, which has some defects, such as the query efficiency is not high, not suitable for high-dimensional space queries and so on. In this paper, we analysis the current research results of home and abroad, and give the point of this article based on the original studies, the contents include the following aspects.Firstly, in order to achieve efficiently reverse nearest neighbor queries, this paper presents a new index structure VAR~*-tree. The main improvement is the introduction of the excellent performance of the SR-tree. Its construction process includes two steps, one is the quantification and compression of the raw data, the other is using SR -tree to manage approximated data, which is to construct an SR-tree with similar data. This index structure has some advantages, greatly reducing the storage space for the quantitative and compression raw data, and the index is more suitable for the RNN than before. Experiments show that VAR~*-tree is more suitable of the queries than SR-tree, and it also has smaller space.Secondly, the paper gives nearest neighbor (VAR~*NN) and k nearest neighbor query algorithms (VAR~*KNN) based on the VAR~*- tree. The experiments proof that algorithms are more efficient than the previous NN algorithms.Again, it gives reverse nearest neighbor query algorithm (VAR~*RNN) based on the VAR~*-tree, and the insertion and deletion algorithms about VAR~*RNN algorithm. The experiments show that query efficiency of VAR~*RNN is better than the previous algorithms in 2-D and 11-dimensional space.In short, this paper presents a new index structure VAR~*-tree, its performance is superior, more suitable for nearest neighbor queries and reverse nearest neighbor queries, to improve the efficiency of their queries. The query efficiency of RNN and NN has a high improvement, and there is a good performance especially in high-dimensional space query.