Study On Moving K-Nearest-Neighbor Queries Over Line Segments In Spatial Databases

With the popularity of personal electronic devices and the development of communication technology, location based services (LBS) have been ubiquitous in our daily life, such as emergency medical service, GPS navigation and people tracking. Among which, moving k nearest neighbor queries in spatial databases have attracted wide attention in academia and industry due to the huge demand of it. All the current works on moving k nearest neighbor queries model the query objects as points. Nevertheless, the query objects in real world could be complicated linear objects, such as rivers, highways, etc. In this case, the traditional method will not be able to provide effective services. In this article, the complex linear objects are modeled as line segments or polylines consisting of a set of line segments, and moving k nearest neighbor queries over line segments in spatial databases have been studied from aspects of line distance calculation and line safe region construction.Firstly, this article formally defines the basic concept of queries over line segments in spatial databases. Then aiming at the complexity of calculating distance between a point and a line segment, the concept of line-segment divided region has been proposed to separately calculate the distance between points and line segments. After that an algorithm of constructing the safe region of moving k nearest neighbor queries has been presented, which is named LRkNN. The LRkNN algorithm which is on the basis of RangeNN, can construct a local safe region of line segments by accessing only a part of data objects. LRkNN can effectively improve the efficiency of the construction of safe region of line segments on the premise of ensuring the accuracy and effectiveness of query results. In addition, in order to support the dynamic changes of data objects, the concept of impact region is proposed based on safe region. If the changing data objects are not contained in the impact region, the recalculation of query results is not needed. The superiority of LRkNN in efficiency and accuracy is verified by the experiments. Compared with the sampling based method, LRkNN increases at least one order of magnitude in response time, I/O costs and communication costs. To improve the usability of moving k nearest neighbor queries, a rank of query results is usually needed. Therefore a LIRU algorithm is presented by extending the IRU algorithm to support the sorting of line segment objects. Then, the LV*-Diagram based on V*-Diagram and the algorithm LMkNN are proposed to construct an approximate safe region by intersecting the region constructed by LIRU and safe region with regard to line segment, which can ensure the accuracy and rank of the query results. At last, it is put forword the concept of polyline divided region in which moving k nearest neighbor queries over polyline is simplified to queries over a single line segment. The moving k nearest neighbor queries over polyline are handled by constructing safe region of line segment using LV*-Diagram in each polyline divided region. LV*-Diagram can also support dynamical addition and deletion of data objects. If the changing data objects are not contained in the safe region with regard to line segment, the recalculation of query results does not needed. The superiority of LRkNN in efficiency and accuracy is verified by the experiments. Compared with the sampling based method, LRkNN increases at least one order of magnitude in response time, I/O costs and communication costs.In summary, by analyzing the typical feature and challenge of moving k nearest neighbor queries over line segment, this article conducts research on key technology of distance calculation between a point and a line segment, safe region construction, the orderliness of query result and the dynamic maintenance of query objects and improve the overall efficiency of query processing.