摘要
地图匹配算法常用于离线轨迹数据挖掘和在线导航中的轨迹位置校正。基于隐马尔可夫模型（HMM）的地图匹配算法（HMM-MMs）是最广泛使用的方法。然而，由于需要频繁计算相邻轨迹点之间的最短路径，HMM-MMs在效率上存在局限性。为了解决这个问题，我们提出了HMM-PMM，这是一种基于MapReduce和HMM的分布式地图匹配框架。首先，根据起点和终点将候选点对进行分组；然后根据节点的空间范围和定制的置信椭圆选择相应的最短路径算法（Floyd算法或A*算法）；最后，利用复杂网络理论中的融合中心性度量构建捷径，以提高长距离查询时A*算法的效率。实验结果表明，与并行化顺序HMM工作流程的基线方案相比，HMM-PMM的速度提升了高达2.90倍，同时保持了与基线匹配器的输出一致性。本研究表明，在所提出的分组工作流程下，Floyd算法可以有效解决离线轨迹地图匹配中某些最短路径子问题。该框架的主要贡献在于对轨迹点对级别的任务进行分解，并重新组织了最短路径的计算过程。
图形摘要
HMM-PMM是一个基于分布式隐马尔可夫模型（HMM）的大规模轨迹数据匹配框架。它通过将候选点对分组、自适应选择最短路径算法（A*或Floyd算法）以及利用捷径增强A*算法集成到MapReduce工作流程中，来重新组织最短路径的计算。针对北京出租车轨迹的实验表明，HMM-PMM在保持与基线匹配器输出一致性的同时，实现了高达2.90倍的速度提升。
利益冲突
作者声明没有利益冲突。
同行评审
为了保证透明度，这篇论文的同行评审文档可在 https://doi.org/10.1111/nyas.70387 查阅。
