Research Of Reverse Nearest Neighbor Query Based On Line Segment

With the rapid development of remote sensing, GIS, computer technology, communications technology and so on,spatial database technology continues to mature, now it is being applied widely in different field.As an important component of spatial database,the query efficiency of spatial query has been become a bottleneck in the performance of spatial database. As an important technology in spatial query of spatial database, the technology of reverse nearest neighbor query has very important theoretical and applied value, it is always been the focus of the study in related fields.Reverse nearest neighbor is based on nearest neighbor query, at present the query granularity of reverse nearest neighbor query is based on one-dimensional points, for some spatial objects which can be abstracted as points, it can achieve better result through reverse nearest neighbor query, but for some spatial objects which can not be abstracted as points, for example routes,high-speed railway, the result of reverse nearest neighbor query by point-query can not reach a certain degree of accuracy.This paper will research reverse nearest neighbor query which based on line segment from two aspects:First, the methods of nearest neighbor query base on line segment in R-tree index structure are researched. The calculation of the distance between line segment and lie segment turn into the calculation of the distance between point and line segment, to divide the location of the relationship between two line segments by two endpoints of a line segment in the direct affecting area of another line segment. According to inward incline and outward incline of line segments, it is divided into four cases to calculate the distance of two line segments.Second, the methods of reverse nearest neighbor query base on line segment are researched. Present the related definitions of reverse nearest neighbor base on line segment. Proposed another index structure Rcd-tree by analysis two kinds of reverse nearest neighbor query methods. Theorems,the filter rules and query methods are proposed by the characteristics of Rcd-tree index structure, the algorithms description of reverse nearest neighbor query base on Rcd-tree are proposed. Through analysis and experiment on the algorithm's time complexity, the results show that this method can implement the reverse nearest neighbor query based on line segments.