Research On Nearest Neighbor Query Over Road Networks

The latest developments in mobile computing, global position system and geographicinformation system, as well as widespread use of wireless technologies have led to the recentprevalence of Location-Based Services（LBS）. Many of the LBS rely on a family of spatialqueries, termed nearest neighbor (NN) queries, which have attracted the attention of manyscholars and been explored in-depth.Early works focused on the Nearest Neighbor queries in Euclidean spaces. In manyreal-world scenarios, however, queries are restricted to Spatial Networks, and the existingworks on Euclidean spaces can not be directly applied to Spatial Networks. Therefore, queriesin spatial networks have been in-depth study and many effective approaches were proposed.However, the majority of the existing works on queries in Spatial Networks are largelyaffected by the density of objects of interest, even some of which provide worse performanceby growing of k value. Thus, we conduct in-depth research on Nearest Neighbor Query overRoad Networks and, propose the precomputation-based query processing strategy to solve theproblems.Specifically, based on the proposed theorem in the non-intersection subpath, wepresented a novel versatile processing approach based on leaping for searching NNs lists ofintersection points and adjacent intersection points by leveraging of Networks Expansion.Thus, we overcome the problems of existing approaches and effectively reduce theprecomputed cost.Further, we provide an efficient continuous search processing approach by leveragingDivide and Conquer Algorithm to deal with the continuous NN queries based on the theoremin the non-intersection subpath, which directly contributes to the reduction of thepre-computation cost. In consideration of specific characteristic for non-intersection subpath,split points are determined by Divide and Conquer Algorithm. Particularly, the performance ismore superior when the intersection points are distributed sparsely in the network.Finally, we conduct a comprehensive set of simulation experiments that demonstrate thatour approaches are correct and effective in terms of I/O and CPU costs.