Abstract：To satisfy the real-time requirement of k-path nearest neighbor(kPNN) query, the BNNL algorithm based on the precomputed NNlists is proposed in this paper depending on the pre-computation idea, using a bi-directional Dijkstra search scheme to acquire the current the 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 kPNN. The performance of BNLL is more efficient about kPNN query speed, in handling the data objects are densely distributed or the number of k is large.
2010, Vol. 30 
