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.