Research On Nearest Neighbor Queries Based On R-Tree In Spatial Database

The great capacity and complexity of spatial data make conventional database query processing techniques no longer well suited, and require exploiting new query processing approaches. 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. People have proposed various types of spatial database query Processing techniques with different spatial index structure, and most of them are based on the R-tree, such as Nearest Neighbor Query,Reverse Nearest Neighbor Query,Continuous Nearest Neighbor Queries and Closest Pair Query.Currently available nearest neighbor query methods are mostly concentrated in the case that the target object is the actual object and the query object is a point in the space, and in practical application, in many cases the query object is also a real object in the space, so there is a great limitation in these methods. The practical implementation of the algorithm in the query process, due to the selected pruning strategy was not adequate, and often need to access a number of nodes that do not include the nearest neighbor's MBR, thereby increasing the I/O cost of accessing the object in the spatial database and computation cost of calculating the actual distance between of the two spatial objects, resulting in low efficiency of the algorithm.This paper has made improvements in the following areas for the shortcomings of current nearest neighbor algorithm. First of all, in order to better meet the needs of the actual query, this paper replaces the query object model consists of a space-point with a new query object model consists of a specific object, and its distance of the estimated upper bound and lower bound is given for the distance between two specific spatial object. Secondly, the ideological of contour lines is introduced into the nearest neighbor query and put forward the concept of distance-isoline, so as to provide a more accurate estimate for lower bound of the distance between two specific spatial objects. Finally, the paper proposes a pruning strategy based on distance-isoline and gives a specific nearest neighbor query processing algorithms. Finally, the correctness and validity of the algorithm is verified by the experiment.