Journal of Computer Applications ›› 2010, Vol. 30 ›› Issue (07): 1947-1949.
• Database technology • Previous Articles Next Articles
Received:
Revised:
Online:
Published:
王宝文1,韩静静1,陈子军2,刘文远1
通讯作者:
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.
Key words: road networks, NNlists, k-path nearest neighbor(kPNN), spatial databases
摘要: 为满足k路径近邻查询的实时性要求,运用预计算思想提出了基于NNlists的BNNL算法,通过在用户当前位置和目的地结点进行双向Dijkstra扩展得到两点间的最短路径,再通过对最短路径上的路网结点预计算的m近邻进行优化处理,最终得到正确的k路径近邻。该方法提高了k路径近邻查询的查询速度,尤其适用于兴趣点密度较大、k值较大的情况。
关键词: 路网, NNlists, k路径近邻, 空间数据库
王宝文 韩静静 陈子军 刘文远. 基于NNlists的路网k路径近邻查询[J]. 计算机应用, 2010, 30(07): 1947-1949.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/
https://www.joca.cn/EN/Y2010/V30/I07/1947