Research On Nearest Neighbor Query Based On R-Tree

Nearest neighbor query is one of the most important queries in the space database query techniques. It is widely used in many fields, such as the geographical information system (GIS), computer aided design and manufacturing (CAD/CAM), intelligent identification system, and multimedia applications, etc. At the same time, with the rapid development of science and technology, the requirements to the nearest query efficiency go higher and higher. Beginning with studing R-trees, which is the most commonly used in spatial index technology, the search algorithm, node insertion algorithm and node deletion algorithm are discussed on R-trees.And the corresponding pseudo codes are given. And by using the related properties of R-trees, different algorithm processes of R-trees are optimized.The study of this thesis is related to two aspects of the nearest neighbor queries applied most widely in practice: K nearest neighbor query (KNN) and obstacle nearest neighbor query (ONN). In KNN, we studied static K nearest neighbor search and dynamic K nearest neighbor query, and the corresponding algorithms, pseudo-code and the explanation of algorithm are presented. Then we apply the spatial data index technicque R-trees to the K nearest neighbor. By using the minimum distance (MINDIST) and minimum maximum distance (MINMAXDIST) to prune and sort the nodes of R-trees during the query, the pruning rules are set up for the query. Based on those, the KNN query algorithm on R-tree is given, and corresponding pseudo-codes.In researching the nearest neighbor of obstacles, we take polygons as the actual application of obstacles. And the algorithm of determining visible points for polygons is presented. Then we only need to consider visible points of the obstacle polygons, so that there will be a great amount of obstacles spots to be screened out. Moreover by using the query knowledge of R-trees to classify the visible points and to find out the shortest path.The shortest path is the obstacle distance between prayer points.