Fast Map-Matching Based on Hidden Markov Model

Map matching is the processing of recognizing the true driving route in the road network according to discrete GPS sampling datas. It is a necessary processing step for many relevant applications such as GPS trajectory data analysis and position analysis. The current map-matching algorithms based on HMM (Hidden Markov model) focus only on the accuracy of the matching rather than efficiency. In this paper, we propose a original method: Instead of focusing on a point-by-point, we consider the trajectory compression method to find the key points in the discrete trajectory, and then search for optimal path through the key points. The experiments are implemented on two sets of real dataset and display that our method significantly improve the efficiency compared with HMM algorithm, while keeping matching accuracy.