Research On K-path Nearest Neighbors Search Based On Pre-computation

With the rapid development of global positioning system and communica- tion technology, we can record the positions of moving objects. Various queries of moving objects are provided for applications of GIS, location-based commerce and mobile computing. The k-Path Nearest Neighbor query (k-PNN) as a new query require efficiently answer user's requirements. Thus, algorithms for improving search speed become important; Best-first Network Expansion (BNE) algorithm is proposed by Zaiben Chen et al. In this paper, we employ the idea of pre-computation to enhance the k-PNN query speed.Firstly, the Based on NN lists (BNNL) algorithm based on the precomp- uted NN lists is proposed depending on the pre-computation idea, using a bi-directional Dijkstra search scheme to acquire the current shortest path to destination, then, the nodes in the shortest path are got. At last, these nodes' m nearest neighbors are optimized by a priority queue in order to get the correct k-PNN. Because these nodes' nearest neighbors don't need to search and read from a list quickly, the query speed of BNNL algorithm can be more efficient about k-PNN query.Secondly, Voronoi diagram not only simplize the road network, but also pre-compute some nodes' shortest path. In order to improve the query speed by decline the number of node search nearest neighbors. Thus, the Voronoi-Based k-Path Nearest Neighbor (VBk-PNN) algorithm based on the pre-computed. At last, some nodes in same NVP as a set to search these nodes' nearest neighbor, then these nodes' nearest neighbors are optimized by a priority queue in order to get the correct k-PNN.Finally, those based on pre-computation methods of k-PNN proposed above are compared with the existing method of BNE. As a result, the performance of BNNL and VBk-PNN algorithms are more efficient about k-PNN query speed than BNE.