Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
An Interactive Voting-based Map Matching Algorithm

Jing Yuan, Yu Zheng, Chengyang Zhang, Xing Xie, and Guangzhong Sun


Matching a raw GPS trajectory to roads on a digital map is often referred to as the Map Matching problem. However, the occurrence of the low-sampling-rate trajectories (e.g. one point per 2 minutes) has brought lots of challenges to existing map matching algorithms. To address this problem, we propose an Interactive Voting-based Map Matching (IVMM) algorithm based on the following three insights: 1) The position context of a GPS point as well as the topological information of road networks, 2) the mutual influence between GPS points (i.e., the matching result of a point references the positions of its neighbors; in turn, when matching its neighbors, the position of this point will also be referenced), and 3) the strength of the mutual influence weighted by the distance between GPS points (i.e., the farther distance is the weaker influence exists). In this approach, we do not only consider the spatial and temporal information of a GPS trajectory but also devise a voting-based strategy to model the weighted mutual influences between GPS points. We evaluate our IVMM algorithm based on a user-labeled real trajectory dataset. As a result, the IVMM algorithm outperforms the related method (ST-Matching algorithm).


Publication typeInproceedings
Published inMDM 2010

Previous versions

Yin Lou, Chengyang Zhang, Yu Zheng, Xing Xie, Wei Wang, and Yan Huang. Map-Matching for Low-Sampling-Rate GPS Trajectories, Association for Computing Machinery, Inc., 4 November 2009.

> Publications > An Interactive Voting-based Map Matching Algorithm