An Improved KNN Search Algorithm Based on Road Network Distance

In this paper we investigate K nearest neighbor searches in spatial network databases.A new algorithm for KNN queries is proposed.Based on the road network architecture proposed by Papadias et al.,we incorporate the precomputed NN lists into the algorithm for decreasing expensive calculation of the shortest path,and record the information of visited edges in the two lists for avoiding unnecessary disk I/Os.Experiments show that the algorithm outperforms other algorithms in high object density.