摘要
研究了空间网络数据库中的K近邻查询,提出了一种新的基于道路网络距离的KNN查询算法。这种方法以已有的道路网络模型框架为基础,通过预计算NN表,减少了昂贵的最短路径计算,利用两个链表记录已访问弧段的信息,避免了不必要的磁盘I/Os,从而有效地提高了算法效率。实验结果表明,在目标点分布比较密集的情况下,本算法明显优于其他算法。
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.
出处
《武汉大学学报（信息科学版）》
EI
CSCD
北大核心
2008年第4期437-439,共3页
Geomatics and Information Science of Wuhan University
基金
国家973计划资助项目(2006CB705500)
关键词
空间网络数据库
KNN查询
道路网络
spatial network databases
K nearest neighbor queries
road network
