Research On The Furthest Neighbor Query Algorithm Of Spatial Database

As the frontier technology of data management, Database Index technology is known well until the end of 1960. In the recent years, it has been an important part of the foundation domains in the world's computer applications. Spatial database has become the important branch of modern databases for some special applications, and the extensive researches on its many fields such as its theory, its structures and implementation technology, have been done. Now the research scope of the nearest neighbor query of spatial database object has been extended to high dimensional spaces, which cover the nearest neighbor, the nearest pair, the approximate nearest neighbor, the network nearest neighbor, the constrained nearest neighbor, the moving nearest neighbor, etc. All of above research topics are based on the nearest query, but in the real life and scientific research, the furthest neighbor problem is not deeply developed.The furthest neighbor and the reverse furthest neighbor query for the planar point were deeply researched in this paper. At the same time the line segment query method was analyzed. The line segment furthest neighbor query in the plane was put forward on the basis of point to point neighbor query problem, point to line segment neighbor query problem, and line to line neighbor query problem. Through systematic organization of different algorithms, combining the advantages of three algorithms and the executable way, and integrating the purpose of this studying, the article presents theoretical analysis and new query algorithms.Firstly, The position relations between the query point and the MBRs of R-trees were deeply analyzed. The pruning rules for furthest neighbor queries were given.The furthest query algorithm based on R-tree was established based on these pruning rules. Moreover, through the establishment of data cube to study furthest neighbor query, the pruning rules were established, based on which the furthest neighbor query algorithm between point and point.Secondly, combining of the reverse nearest neighbor query on point and the computational geometry query algorithm, summarizing the advantages andimproving the algorithm, the new pruning rules of the reverse furthest neighbor query were presented in the thesis, which sets up a more efficient query algorithm fort the reverse furthest neighbor query.In the end, the furthest neighbor query algorithm for segments was given, based on Voronoi diagram.