HMM-PMM: A Parallel Hidden Markov Model-Based Map-Matching Framework for Large-Scale Trajectory Data

Map-matching algorithms are commonly used for trajectory position correction in offline trajectory data mining and online navigation. Hidden Markov model (HMM)-based map-matching algorithms (HMM-MMs) are the most widely used approaches. However, HMM-MMs face efficiency limitations due to frequent shortest-path calculations between candidate point pairs of adjacent trajectory points. To address this, we propose HMM-PMM, a distributed map-matching framework based on MapReduce and HMM. First, candidate point pairs are grouped by their origin-destination nodes. Next, the appropriate shortest-path algorithm, either Floyd's algorithm or A*, is selected based on the spatial range of nodes and a customized confidence ellipse. Finally, shortcuts are constructed based on fusion centrality measures from complex network theory and utilized to improve A* efficiency for long-distance queries. Experimental results show that HMM-PMM achieves up to a 2.90× speedup compared to a baseline that parallelizes the sequential HMM workflow, while preserving output consistency with the baseline matcher. This research demonstrates that, under the proposed grouped workflow, Floyd's algorithm can be effective for a class of shortest-path subproblems in offline trajectory map matching. The main contribution of the framework lies in trajectory-point-pair-level task decomposition and in the corresponding reorganization of shortest-path computation.