基于轨迹微分段模型的快速地图匹配方法

doi:10.11896/jsjkx.250900115

摘要/Abstract

摘要： 地图匹配是智能交通系统中的核心技术之一,旨在将GPS轨迹数据映射至城市路网上,消除定位误差并还原实际行驶路径。随着GPS轨迹数据量的爆炸性增长,传统的基于隐马尔可夫模型(HMM)的地图匹配方法因高计算成本和时序依赖性问题,难以满足实时处理要求。为此,提出了一种基于轨迹微分段模型的快速地图匹配方法(Micro-Segment Fast Matching,MSFM)。该方法基于滑动窗口机制,将轨迹分解为固定长度的微轨迹段,在分布式计算环境中利用向量化计算方法,在兼顾地图匹配准确性的条件下大幅度提升了计算效率。实验结果表明,在给定的分布式集群环境下,MSFM实现了约110 000点/秒的地图匹配速度,比基准算法快约7倍,同时保持了95.86%的匹配准确率。MSFM方法通过改进轨迹数据的存储结构,在高效实时处理大规模轨迹数据方面具有显著的性能优势。

关键词: 地图匹配, 轨迹微分段, 隐马尔可夫模型, 分布式计算, 向量化计算

Abstract: Map matching is one of the core technologies in intelligent transportation systems,aiming to map GPS trajectory data to urban road networks,eliminate positioning errors,and reconstruct actual driving paths.With the explosive growth of GPS tra-jectory data volume,traditional HMM(Hidden Markov Model)-based map matching methods struggle to meet real-time proces-sing requirements due to high computational costs and temporal dependency constraints.To address this,this paper proposes a fast map matching method based on a trajectory micro-segment model(Micro-Segment Fast Matching,MSFM).By leveraging a sliding window mechanism,the proposed method decomposes trajectories into fixed-length micro-segments and employs vecto-rized computation techniques in a distributed computing environment.This approach significantly improves computational efficiency while maintaining map matching accuracy.Experimental results demonstrate that,under a distributed cluster configuration,MSFM achieves a map matching speed of approximately 110 000 points per second,which is 7 times faster than baseline algorithms,while retaining a 95.86% matching accuracy.By optimizing the storage structure of trajectory data,the MSFM method exhibits significant performance advantages in real-time processing of large-scale trajectory data with high efficiency.

Key words: Map matching, Micro-segment, Hidden Markov model, Distributed computing, Vectorized computation

中图分类号:

TP311.13

康军, 高晟恺, 来嘉宝. 基于轨迹微分段模型的快速地图匹配方法[J]. 计算机科学, 2026, 53(4): 252-259. https://doi.org/10.11896/jsjkx.250900115

KANG Jun, GAO Shengkai, LAI Jiabao. Fast Map Matching Method Based on Trajectory Micro-segment Model[J]. Computer Science, 2026, 53(4): 252-259. https://doi.org/10.11896/jsjkx.250900115

参考文献

[1]ZHENG Y,ZHOU X.Computing with spatial trajectories[M].Springer Science & Business Media,2011.
[2]LUO Q,HE S,HAN X,et al.LSTTN:A long-short term transformer-based spatiotemporal neural network for traffic flow forecasting[J].Knowledge-Based Systems,2024,293:111637.
[3]JUAN Z,ZHANG J,GAO M.A multimodal travel route recommendation system leveraging visual Transformers and self-attention mechanisms[J].Frontiers in Neurorobotics,2024,18:1439195.
[4]QUDDUS M A,OCHIENG W Y,NOLAND R B.Current map-matching algorithms for transport applications:State-of-the art and future research directions[J].Transportation Research part C:Emerging Technologies,2007,15(5):312-328.
[5]RABINER L,JUANG B.An introduction to hidden Markovmodels[J].IEEE Assp Magazine,1986,3(1):4-16.
[6]NEWSON P,KRUMM J.Hidden Markov map matchingthrough noise and sparseness[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.2009.
[7]ZAHARIA M,CHOWDHURY M,DAS T,et al.Resilient distributed datasets:A {Fault-Tolerant} abstraction for {In-Memory} cluster computing[C]//Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation(NSDI 12).2012.
[8]YANG C,GIDOFALVI G.Fast map matching,an algorithm integrating hidden Markov model with precomputation[J].International Journal of Geographical Information Science,2018,32(3):547-70.
[9]GUTTMAN A.R-trees:A dynamic index structure for spatialsearching[C]//Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data.1984.
[10]FINKEL R A,BENTLEY J L.Quad trees a data structure for retrieval on composite keys[J].Acta Knformatica,1974,4:1-9.
[11]BALKIĆ Z,ŠOŠTARIĆ D,HORVAT G.GeoHash and UUID identifier for multi-agent systems[C]//Proceedings of the Agent and Multi-Agent Systems Technologies and Applications:6th KES International Conference(KES-AMSTA 2012).2012:25-27.
[12]ISHIGURO T,SASAI T,FUKUSHIMA S,et al.Leveragingtrajectory simplification for efficient map-matching on road network[C]//Proceedings of the 2024 25th IEEE International Conference on Mobile Data Management(MDM).2024.
[13]KOLLER H,WIDHALM P,DRAGASCHNIG M,et al.Fast hidden Markov model map-matching for sparse and noisy trajectories[C]//Proceedings of the 2015 IEEE 18th International Conference on Intelligent Transportation Systems.2015.
[14]HART P E,NILSSON N J,RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics,1968,4(2):100-107.
[15]GOLDBERG A V,HARRELSON C.Computing the shortestpath:A search meets graph theory[C]//Proceedings of the SODA.2005.
[16]DOGRAMADZI M,KHAN A.Accelerated map matching forGPS trajectories[J].IEEE Transactions on Intelligent Transportation Systems,2021,23(5):4593-4602.
[17]FU X,ZHANG J,ZHANG Y.An Online Map Matching Algorithm Based on Second-Order Hidden Markov Model[J].Journal of Advanced Transportation,2021,2021(1):9993860.
[18]HUANG J,QIAO S,YU H,et al.Parallel map matching onmassive vehicle gps data using mapreduce[C]//Proceedings of the 2013 IEEE 10th International Conference on High Perfor-mance Computing and Communications & 2013 IEEE Internatio-nal Conference on Embedded and Ubiquitous Computing.2013.
[19]DEAN J,GHEMAWAT S.MapReduce:simplified data proces-sing on large clusters[J].Communications of the ACM,2008,51(1):107-113.
[20]ALVES P D,QUOC V N H,ZHENG B,et al.A framework for parallel map-matching at scale using Spark[J].Distributed and Parallel Databases,2019,37:697-720.
[21]YU J,WU J,SARWAT M.Geospark:A cluster computingframework for processing large-scale spatial data[C]//Procee-dings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems.2015.

相关文章 15

[1]	张曼静, 何玉林, 李旭, 黄哲学. 基于节点抽样的分布式二阶段聚类方法 Distributed Two-stage Clustering Method Based on Node Sampling 计算机科学, 2025, 52(2): 134-144. https://doi.org/10.11896/jsjkx.240800040
[2]	王瀚橙, 戴海鹏, 陈志鹏, 陈树森, 陈贵海. 基于MapReduce的大规模网络社区发现算法 Large-scale Network Community Detection Algorithm Based on MapReduce 计算机科学, 2024, 51(4): 11-18. https://doi.org/10.11896/jsjkx.231100049
[3]	韩琦琦, 刘鑫. 异地高速互联环境下的海气耦合模式应用 Application of Air-Sea Coupled Mode in High-speed Interconnection Environment 计算机科学, 2023, 50(11A): 221000136-5. https://doi.org/10.11896/jsjkx.221000136
[4]	费星瑞, 谢逸. 基于HMM-NN的用户点击流识别 Click Streams Recognition for Web Users Based on HMM-NN 计算机科学, 2022, 49(7): 340-349. https://doi.org/10.11896/jsjkx.210600127
[5]	王欣, 向明月, 李思颖, 赵若成. 基于隐马尔可夫模型的铁路出行团体关系预测研究 Relation Prediction for Railway Travelling Group Based on Hidden Markov Model 计算机科学, 2022, 49(6A): 247-255. https://doi.org/10.11896/jsjkx.210500001
[6]	王如斌, 李瑞远, 何华均, 刘通, 李天瑞. 面向海量空间数据的分布式距离连接算法 Distributed Distance Join Algorithm for Massive Spatial Data 计算机科学, 2022, 49(1): 95-100. https://doi.org/10.11896/jsjkx.210100060
[7]	钱甜甜, 张帆. 基于分布式边缘计算的情绪识别系统 Emotion Recognition System Based on Distributed Edge Computing 计算机科学, 2021, 48(6A): 638-643. https://doi.org/10.11896/jsjkx.201000010
[8]	苑晨宇, 谢在鹏, 朱晓瑞, 屈志昊, 徐媛媛. 一种基于分布式编码的卷积优化算法 Convolutional Optimization Algorithm Based on Distributed Coding 计算机科学, 2021, 48(2): 47-54. https://doi.org/10.11896/jsjkx.200800187
[9]	张成伟, 罗凤娥, 代毅. 基于数据挖掘的指定航班计划延误预测方法 Prediction Method of Flight Delay in Designated Flight Plan Based on Data Mining 计算机科学, 2020, 47(11A): 464-470. https://doi.org/10.11896/jsjkx.200600001
[10]	张经, 杨健, 苏鹏. 语音识别中单音节识别研究综述 Survey of Monosyllable Recognition in Speech Recognition 计算机科学, 2020, 47(11A): 172-174. https://doi.org/10.11896/jsjkx.200200006
[11]	严盛隆, 于娟, 周后盘. IIVMM:针对低频GPS轨迹的改进交互式投票匹配算法 IIVMM:An Improved Interactive Voting-based Map Matching Algorithm for Low-sampling-rate GPS Trajectories 计算机科学, 2019, 46(9): 325-332. https://doi.org/10.11896/j.issn.1002-137X.2019.09.050
[12]	李博嘉, 张仰森, 陈若愚. 一种可指定分布的海量数据生成方法 Method for Generating Massive Data with Assignable Distribution 计算机科学, 2019, 46(8): 56-63. https://doi.org/10.11896/j.issn.1002-137X.2019.08.009
[13]	岳鑫, 杜军威, 胡强, 王延平. 一种故障树结构匹配算法及其应用 Fault Tree Structure Matching Algorithm and Its Application 计算机科学, 2018, 45(9): 202-206. https://doi.org/10.11896／j.issn.1002-137X.2018.09.033
[14]	宫法明,朱朋海. 基于自适应隐马尔可夫模型的石油领域文档分词 Word Segmentation Based on Adaptive Hidden Markov Model in Oilfield 计算机科学, 2018, 45(6A): 97-100.
[15]	邵炜晖,许维胜,徐志宇,王宁,农静. 基于区块链的虚拟电厂模型研究 Study on Virtual Power Plant Model Based on Blockchain 计算机科学, 2018, 45(2): 25-31. https://doi.org/10.11896/j.issn.1002-137X.2018.02.005

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed