采用R树和轨迹分段的HMM高效地图匹配方法

针对传统隐马尔可夫模型(hidden-Markov model,HMM)地图匹配算法无法高效处理大量轨迹数据的问题，提出了一种改进的HMM地图匹配算法。采用R树空间索引方法为路网建立空间索引，基于轨迹点位置变化率对GPS轨迹数据进行分段，并利用R树索引快速确定子轨迹所属的候选路段，在子轨迹中挑选关键点代替整段子轨迹判断所属路段，根据结果完成各子轨迹的地图匹配。仿真结果表明：与传统HMM地图匹配算法相比，改进算法可以同时减少道路搜索和轨迹点遍历的工作量，大幅提高算法效率。

Efficient HMM Map Matching Method Using R-tree and Trajectory Segmentation

In view of the incapability of traditional methods to efficiently process massive trajectory data, an improved HMM (hidden-Markov model) map matching algorithm is proposed. Spatial index for road networks is established through R-tree spatial index. GPS trajectory data are segmented based on the position change rates of trajectory points. R-tree index is used to quickly determine the candidate road section that sub-trajectories belong to, and the key points of the sub-trajectories instead of the entire sub-trajectories are selected to judge which road the sub-trajectories should be matched with. The map matching of each sub-trajectory is carried out on the basis of the former results. The algorithm is verified by a simulation experiment using Beijing's floating car data and OpenStreetMap data. Experimental result shows that the proposed algorithm can reduce the workload of road search and trajectory point traversal and can greatly improve the algorithmic efficiency.