《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (11): 3403-3410.DOI: 10.11772/j.issn.1001-9081.2023101503

• 数据科学与技术 • 上一篇    下一篇

面向动态路网的移动对象分布式k近邻查询算法

陈国祥, 于自强(), 赵浩宇   

  1. 烟台大学 计算机与控制工程学院,山东 烟台 264005
  • 收稿日期:2023-11-03 修回日期:2024-01-14 接受日期:2024-01-24 发布日期:2024-11-13 出版日期:2024-11-10
  • 通讯作者: 于自强
  • 作者简介:陈国祥(1998—),男,山东青岛人,硕士研究生,主要研究方向:时空数据处理
    赵浩宇(1999—),男,山东临沂人,硕士研究生,主要研究方向:时空数据处理。
  • 基金资助:
    国家自然科学基金资助项目(62172351)

Distributed k-nearest neighbor query algorithm for moving objects in dynamic road network

Guoxiang CHEN, Ziqiang YU(), Haoyu ZHAO   

  1. School of Computer and Control Engineering,Yantai University,Yantai Shandong 264005,China
  • Received:2023-11-03 Revised:2024-01-14 Accepted:2024-01-24 Online:2024-11-13 Published:2024-11-10
  • Contact: Ziqiang YU
  • About author:CHEN Guoxiang, born in 1998, M. S. candidate. His research interests include spatio-temporal data processing.
    ZHAO Haoyu, born in 1999, M. S. candidate. Her research interests include spatio-temporal data processing.
  • Supported by:
    National Natural Science Foundation of China(62172351)

摘要:

动态路网k近邻(kNN)查询是许多基于位置的服务(LBS)中的一个重要问题。针对该问题,提出一种面向动态路网的移动对象分布式kNN查询算法DkNN(Distributed kNN)。首先,将整个路网划分为部署于集群中不同节点中的多个子图;其次,通过并行地搜索查询范围所涉及的子图得到精确的kNN结果;最后,优化查询的搜索过程,引入查询范围剪枝策略和查询终止策略。在4个道路网络数据集上与3种基线算法进行了充分对比和验证。实验结果显示,与TEN*-Index (Tree dEcomposition based kNN* Index)算法相比,DkNN算法的查询时间减少了56.8%,路网更新时间降低了3个数量级。DkNN算法可以快速响应动态路网中的kNN查询请求,且在处理路网更新时具有较低的更新成本。

关键词: 动态道路网络, k近邻查询, 分布式环境, 基于位置的服务, 时空数据处理

Abstract:

The k-Nearest Neighbor (kNN) query in dynamic road network is an important problem in many Location-Based Services (LBS). To address this problem, a distributed moving object kNN query algorithm named DkNN (Distributed k-Nearest Neighbor) was proposed for dynamic road networks. Firstly, the entire road network was divided into multiple subgraphs deployed in different nodes in the cluster. Then, the accurate kNN results were obtained by searching the subgraphs involved in the query range in parallel. Finally, the searching process of the query was optimized, and the query range pruning strategy as well as the query termination strategy was introduced. A full comparison and validation with three baseline algorithms on four road network datasets was performed. Experimental results show that the DkNN algorithm reduces the query time by 56.8% and the road network update time by 3 orders of magnitude compared to TEN*-Index (Tree dEcomposition based kNN* Index) algorithm. The DkNN algorithm can quickly respond to kNN query requests in dynamic road network and has a low update cost when dealing with road network updates.

Key words: dynamic road network, k Nearest Neighbor (kNN) query, distributed environment, Location-Based Services (LBS), spatio-temporal data processing

中图分类号: