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

李瑞远; 朱浩文; 王如斌; 陈超; 郑宇

doi:10.7544/issn1000-1239.20210904

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

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

¹(重庆大学计算机学院重庆 400044)
²(京东城市(北京)数字科技有限公司北京 100176)
³(北京京东智能城市大数据研究院北京 100176) (ruiyuan.li@cqu.edu.cn)

基金项目: 国家重点研发计划项目(2019YFB2101801)；国家自然科学基金项目(61976168,61872050,62172066)

详细信息

中图分类号: TP391
计量
- 文章访问数: 827
- HTML全文浏览量: 8
- PDF下载量: 361
出版历程
- 发布日期: 2022-01-31

Fast and Distributed Map-Matching Based on Contraction Hierarchies

Li Ruiyuan^1,2,3,
Zhu Haowen^2,3,
Wang Rubin^2,3,
Chen Chao¹,
Zheng Yu^2,3

¹(College of Computer Science, Chongqing University, Chongqing 400044)
²(JD iCity, JD Technology, Beijing 100176)
³(JD Intelligent Cities Research, Beijing 100176)

Funds: 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.
- map-matching /
- trajectory data /
- distributed computing /
- contraction hierarchies /
- urban computing