Algorithm Research On Nearest Neighbor Query And Reverse Nearest Neighbor Query

The great capacity and the complexity of spatial data make conventional database query processing techniques no longer well suited, and new query processing approaches are required to be exploited. Therefore, how to provide all kinds of efficient query processing techniques for spatial and spatiotemporal objects is one of research hotspots in the area of spatial databases currently. Various types of spatial database query processing techniques with different spatial index structures have been proposed, and most of them are based on the R-tree, such as nearest neighbor query, reverse nearest neighbor query, continuous nearest neighbor query, k nearest neighbor query, dynamic nearest neighbor query and closest pair query. Motivated by this problem, we have done some research.Firstly, nearest neighbor query is studied in this thesis. The algrithms of nearest neighbor query, continuous nearest neighbor query and dynamic nearest neighbor query are not only summed up systematically but also improved. Classical algorithms of reverse nearest neighbor queries are studied. The basic methods of reverse nearest neighbor query are mastered. On the basis of analyzing the deficiency of the existing algorithms, the following algorithms can be proposed.Secondly, through the research of nearest neighbor queries based on Voronoi diagram, the algorithm of reverse nearest neighbor query based on Voronoi diagram and Delaunay graph is obtained. And through combining the Voronoi diagram and Rdnn-tree, the definition of VRdnn-tree is given. At first, by using this index structure, the range of reverse nearest neighbor can be minished in the massive spatial data sets. Then by using Voronoi diagram and Delaunay graph to search reverse nearest neighbors, the time complexity of this algorithm can be reduced much.Finally, the algorithm of reverse nearest neighbor query based on Voronoi diagram is proposed. Voronoi diagram and the convex hulls of dataset are used for reverse nearest neighbor search. Through the location between query point and convex hulls, many points can be cut off. Algorithm and judgment method are given for the changes to the reverse nearest neighbors of the given query points caused by adding or deleting data points from the data set. To more easily search for these points in a database, corresponding database storage structures are designed.Comparative analysis shows that the above two algorithms are both suitable to deal with the reverse nearest neighbor queries of data points on planar surfaces and complex curverd surfaces. And these methods are more advantageous than others for dealing with the case of many query points.