An improved KNN search algorithm based on road network distance

作者：Xiao Hui^*; Yang Bisheng

来源：Geomatics and Information Science of Wuhan University, 2008, 33(4): 437-439.

• K nearest neighbor queries
• Road network architecture
• Road network distance
• Spatial network databases

In this paper we investigate K nearest neighbor searches in spatial network data-bases. 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.

• 出版日期2008