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

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

Fast and Distributed Map-Matching Based on Contraction Hierarchies

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.