基于NNlists的路网k路径近邻查询

计算机应用 ›› 2010, Vol. 30 ›› Issue (07): 1947-1949.

基于NNlists的路网k路径近邻查询

王宝文¹,韩静静¹,陈子军²,刘文远¹

1. 燕山大学信息科学与工程学院
2.

收稿日期:2010-01-21 修回日期:2010-03-08 发布日期:2010-07-01 出版日期:2010-07-01
通讯作者: 韩静静

NNlists-based k-path nearest neighbor query in road networks

Received:2010-01-21 Revised:2010-03-08 Online:2010-07-01 Published:2010-07-01

摘要/Abstract

摘要： 为满足k路径近邻查询的实时性要求，运用预计算思想提出了基于NNlists的BNNL算法，通过在用户当前位置和目的地结点进行双向Dijkstra扩展得到两点间的最短路径，再通过对最短路径上的路网结点预计算的m近邻进行优化处理，最终得到正确的k路径近邻。该方法提高了k路径近邻查询的查询速度，尤其适用于兴趣点密度较大、k值较大的情况。

关键词: 路网, NNlists, k路径近邻, 空间数据库

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

王宝文韩静静陈子军刘文远. 基于NNlists的路网k路径近邻查询[J]. 计算机应用, 2010, 30(07): 1947-1949.

[1]	赵浩宇, 于自强, 陈晓萌, 陈国祥, 朱慧, 李博涵. 支持关键词搜索的top-K条最优路线查询问题[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2455-2465.
[2]	田润泽, 周宇龙, 朱洪, 薛岗. 基于局部信息的服务迁移路径选择算法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2168-2174.
[3]	刘沛骞, 王水莲, 申自浩, 王辉. 基于轨迹扰动和路网匹配的位置隐私保护算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1546-1554.
[4]	陈国祥, 于自强, 赵浩宇. 面向动态路网的移动对象分布式k近邻查询算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3403-3410.
[5]	陈方疏, 张为, 胡小明, 张宇飞, 孟宪凯, 石林祥. 加权路网空间中动态聚集最近邻居查询算法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2026-2033.
[6]	付宇, 王红. 位置隐私保护的虚拟轨迹填充算法[J]. 计算机应用, 2019, 39(8): 2318-2325.
[7]	霍峥, 张坤, 贺萍, 武彦斌. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3): 763-768.
[8]	冯钧, 李顶圣, 陆佳民, 张立霞. 基于HBase的路网移动对象时空索引方法[J]. 计算机应用, 2018, 38(6): 1575-1583.
[9]	李佳佳, 刘晓静, 刘向宇, 夏秀峰, 朱睿. 基于动态选择启发值的改进TD-FTT算法[J]. 计算机应用, 2018, 38(1): 120-125.
[10]	毕崇春, 孟祥福, 张霄雁, 唐延欢, 唐晓亮, 梁海波. 基于耦合相关度的空间数据查询结果自动分类方法[J]. 计算机应用, 2018, 38(1): 152-158.
[11]	霍峥, 崔洪雷, 贺萍. 基于语义位置保护的轨迹隐私保护的k-CS算法[J]. 计算机应用, 2018, 38(1): 182-187.
[12]	霍峥, 王卫红, 曹玉辉. PTDC:路网环境中感知隐私的轨迹数据采集技术[J]. 计算机应用, 2017, 37(9): 2567-2571.
[13]	徐伟, 李文根, 张毅超, 关佶红. 路网中位置不确定的二元反kNN查询[J]. 计算机应用, 2017, 37(2): 341-346.
[14]	周沙, 王润, 甄文杰. 顾及主观判断延误的行人路径选择模型[J]. 计算机应用, 2016, 36(4): 1146-1150.
[15]	朱海泉, 李文根, 张毅超, 关佶红. 基于路网的群体出行计划查询算法[J]. 计算机应用, 2015, 35(11): 3146-3150.