Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Map-Matching for Low-Sampling-Rate GPS Trajectories

Yin Lou, Chengyang Zhang, Yu Zheng, Xing Xie, Wei Wang, and Yan Huang


Map-matching is the process of aligning a sequence of observed user positions with the road network on a digital map. It is a fundamental pre-processing step for many applications, such as moving object management, traffic flow analysis, and driving directions. In practice there exists huge amount of low-sampling-rate (e.g., one point every 2-5 minutes) GPS trajectories. Unfortunately, most current map-matching approaches only deal with high-sampling-rate (typically one point every 10-30s) GPS data, and become less effective for low-sampling-rate points as the uncertainty in data increases. In this paper, we propose a novel global map-matching algorithm called ST-Matching for low-sampling-rate GPS trajectories. ST-Matching considers (1) the spatial geometric and topological structures of the road network and (2) the temporal/speed constraints of the trajectories. Based on spatio-temporal analysis, a candidate graph is constructed from which the best matching path sequence is identified. We compare ST-Matching with the incremental algorithm and Average-Fréchet-Distance (AFD) based global map-matching algorithm. The experiments are performed both on synthetic and real dataset. The results show that our ST-matching algorithm significantly outperform incremental algorithm in terms of matching accuracy for low-sampling trajectories. Meanwhile, when compared with AFD-based global algorithm, ST-Matching also improves accuracy as well as running time.


Publication typeInproceedings
Published inACM SIGSPATIAL GIS 2009
PublisherAssociation for Computing Machinery, Inc.

Newer versions

Jing Yuan, Yu Zheng, Chengyang Zhang, Xing Xie, and Guangzhong Sun. An Interactive Voting-based Map Matching Algorithm, IEEE, 25 May 2010.

Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, and Yan Huang. T-Drive: Driving Directions Based on Taxi Trajectories, Association for Computing Machinery, Inc., 1 November 2010.

> Publications > Map-Matching for Low-Sampling-Rate GPS Trajectories