ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2022, Vol. 59 ›› Issue (2): 342-361.doi: 10.7544/issn1000-1239.20210904

所属专题: 2022空间数据智能专题

• 人工智能 • 上一篇    下一篇

基于路网层次收缩的快速分布式地图匹配算法

李瑞远1,2,3,朱浩文2,3,王如斌2,3,陈超1,郑宇2,3   

  1. 1(重庆大学计算机学院 重庆 400044);2(京东城市(北京)数字科技有限公司 北京 100176);3(北京京东智能城市大数据研究院 北京 100176) (ruiyuan.li@cqu.edu.cn)
  • 出版日期: 2022-02-01
  • 基金资助: 
    国家重点研发计划项目(2019YFB2101801);国家自然科学基金项目(61976168,61872050,62172066)

Fast and Distributed Map-Matching Based on Contraction Hierarchies

Li Ruiyuan1,2,3, Zhu Haowen2,3, Wang Rubin2,3, Chen Chao1, Zheng Yu2,3   

  1. 1(College of Computer Science, Chongqing University, Chongqing 400044);2(JD iCity, JD Technology, Beijing 100176);3(JD Intelligent Cities Research, Beijing 100176)
  • Online: 2022-02-01
  • Supported by: 
    This work was supported by the National Key Research and Development Program of China (2019YFB2101801) and the National Natural Science Foundation of China (61976168, 61872050, 62172066).

摘要: 地图匹配是轨迹数据挖掘的基本操作,在许多空间数据智能场景中都非常有用.基于隐马尔可夫模型(hidden Markov model, HMM)的地图匹配算法具有较高的准确率,应用最为广泛,但其计算效率较低,难以应对实时性要求较高的大规模轨迹情形.提出了一个基于路网层次收缩的分布式地图匹配框架CHMM,能够对大规模的轨迹数据实现快速地图匹配.具体而言,提出了一个简单但有效的分区方案,能够解决分布式场景下轨迹数据分布不平衡的问题;提出了一个基于路网层次收缩的多对多最短路径查询算法,能够保证结果不变的情况下,显著提升基于HMM的地图匹配算法的效率.采用真实的路网数据和轨迹数据做了充分的实验,实验结果表明:CHMM算法具有更快的计算效率和更强的可扩展性.CHMM算法落回到了真实的产品中,支持了多个项目的落地.我们也开源了核心代码,并提供了一个在线演示系统.

关键词: 地图匹配, 轨迹数据, 分布式计算, 层次收缩, 城市计算

Abstract: Map-Matching is a basic operation for trajectory data mining, which is very useful for many spatial intelligent applications. Hidden Markov model (i.e., HMM)-based map-matching is the most widely-used algorithm for its high accuracy. However, HMM-based map-matching is very time-consuming, so it can hardly be applied to real-time scenarios with massive trajectory data. In this paper a contraction hierarchy-based and distributed map-matching framework, i.e., CHMM, is proposed, which map-matches massive trajectories efficiently. Specifically, we first propose a simple but effective partitioning strategy to solve the issue of unbalanced trajectory data distribution. Then, we propose a contraction hierarchy-based many-to-many shortest path search method, which significantly improves the efficiency of HMM-based map-matching while keeps the results unchanged. Extensive experiments are conducted using real road network data and big trajectory data, verifying the powerful efficiency and scalability of CHMM. CHMM has been deployed to our product, supporting various real urban applications. We publish the core source code and provide an online demo system.

Key words: map-matching, trajectory data, distributed computing, contraction hierarchies, urban computing

中图分类号: