HMM‐PMM: A Parallel Hidden Markov Model‐Based Map‐Matching Framework for Large‐Scale Trajectory Data
Annals of the New York Academy of Sciences · 2026
DOI: 10.1111/nyas.70387 ↗Kurz gefasst
Fachartikel in der Zeitschrift Annals of the New York Academy of Sciences, 2026. Verfasst von Ruibo Cong und 4 weiteren Autor:innen. Beteiligte Einrichtung: School of Resource and Environmental Sciences, Wuhan University, Wuhan, China. Hauptthemen laut MEDLINE: Algorithms, Data Mining. Die Arbeit nennt 35 Literaturangaben. Der Volltext ist frei in PubMed Central verfügbar. Gefördert von: National Natural Science Foundation of China, Hubei Provincial Science and Technology Innovation Talents Program, Young Science and Technology Talents Training Special Project.
Abstract (Originalsprache)
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.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Stichwörter der Autor:innen
Autor:innen und Institutionen
- School of Resource and Environmental Sciences, Wuhan University, Wuhan, China.
- Key Laboratory of Geographical Information Systems, Ministry of Education, Wuhan University, Wuhan, China.
- Basic Geographic Information Center, Wuhan Geomatics Institute, Wuhan, China.
- Engineering Technology Innovation Center for 3D Real Scene Construction and Urban Refined Governance, Ministry of Natural Resources, Wuhan, China.
Förderung
- National Natural Science Foundation of China
- Hubei Provincial Science and Technology Innovation Talents Program
- Young Science and Technology Talents Training Special Project
Zitieren
APA
Cong, R., Li, B., Niu, Z., Cai, Z., & Cao, W. (2026). HMM‐PMM: A Parallel Hidden Markov Model‐Based Map‐Matching Framework for Large‐Scale Trajectory Data. Annals of the New York Academy of Sciences. https://doi.org/10.1111/nyas.70387
Vancouver
Cong R, Li B, Niu Z, Cai Z, Cao W. HMM‐PMM: A Parallel Hidden Markov Model‐Based Map‐Matching Framework for Large‐Scale Trajectory Data. Annals of the New York Academy of Sciences. 2026. doi:10.1111/nyas.70387
BibTeX
@article{Cong2026,
author = {Cong, Ruibo and Li, Bozhao and Niu, Zhengjia and Cai, Zhongliang and Cao, Wentao},
title = {HMM‐PMM: A Parallel Hidden Markov Model‐Based Map‐Matching Framework for Large‐Scale Trajectory Data},
journal = {Annals of the New York Academy of Sciences},
year = {2026},
doi = {10.1111/nyas.70387}
}
EUVIMED