基于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]	付宇, 王红. 位置隐私保护的虚拟轨迹填充算法[J]. 计算机应用, 2019, 39(8): 2318-2325.
[2]	霍峥, 张坤, 贺萍, 武彦斌. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3): 763-768.
[3]	冯钧, 李顶圣, 陆佳民, 张立霞. 基于HBase的路网移动对象时空索引方法[J]. 计算机应用, 2018, 38(6): 1575-1583.
[4]	毕崇春, 孟祥福, 张霄雁, 唐延欢, 唐晓亮, 梁海波. 基于耦合相关度的空间数据查询结果自动分类方法[J]. 计算机应用, 2018, 38(1): 152-158.
[5]	霍峥, 崔洪雷, 贺萍. 基于语义位置保护的轨迹隐私保护的k-CS算法[J]. 计算机应用, 2018, 38(1): 182-187.
[6]	李佳佳, 刘晓静, 刘向宇, 夏秀峰, 朱睿. 基于动态选择启发值的改进TD-FTT算法[J]. 计算机应用, 2018, 38(1): 120-125.
[7]	霍峥, 王卫红, 曹玉辉. PTDC:路网环境中感知隐私的轨迹数据采集技术[J]. 计算机应用, 2017, 37(9): 2567-2571.
[8]	徐伟, 李文根, 张毅超, 关佶红. 路网中位置不确定的二元反kNN查询[J]. 计算机应用, 2017, 37(2): 341-346.
[9]	周沙, 王润, 甄文杰. 顾及主观判断延误的行人路径选择模型[J]. 计算机应用, 2016, 36(4): 1146-1150.
[10]	朱海泉, 李文根, 张毅超, 关佶红. 基于路网的群体出行计划查询算法[J]. 计算机应用, 2015, 35(11): 3146-3150.
[11]	李松, 李林, 王淼, 崔环宇, 张丽平. RTC树的构建与不确定近邻关系查询方法[J]. 计算机应用, 2015, 35(1): 115-120.
[12]	王淼黄治国李松. 基于代数理论的三维主方向关系的反关系推理[J]. 计算机应用, 2014, 34(4): 1144-1148.
[13]	张丽平李松赵纪桥郝晓红. 受限区域内的单纯型连续近邻链查询方法[J]. 计算机应用, 2014, 34(2): 406-410.
[14]	刘德高李晓宇. 基于道路网的连续k近邻查询算法[J]. 计算机应用, 2013, 33(07): 1964-1968.
[15]	罗亚男付永庆. 基于分层路网的路径规划算法[J]. 计算机应用, 2013, 33(06): 1763-1766.