An advanced interactive-voting based map matching algorithm for low-sampling-rate GPS data

The availability of GPS data from in-vehicle devices has greatly enriched the location based system applications, in which map matching plays an important role. For the low-sampling-rate GPS data, existing map matching algorithms would have many challenges such as the high error rate and inefficiency on the complex urban road network. This paper presents an advanced map matching algorithm based on interactive-voting for low-sampling-rate data of taxi GPS trajectories. The algorithm employs spatial analysis function, temporal analysis function, and road analysis function with two constraints to measure the relationship between consecutive candidate points in map-matching. The constraints in our algorithm not only reduce much computation but also significantly improve the accuracy of the algorithm. Based on the interaction between GPS sampling points, we propose a novel voting method called candidate edge voting to get the best map matching result. We evaluate our algorithm using a one-month real-world trajectory dataset. The proposed algorithm outperforms in both accuracy and efficiency.