Y. Li, Q. Huang, M. Kerber, L. Zhang and L. Guibas, Large-Scale Joint Map Matching of GPS Traces, In Proceedings of the 21th SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS ’13, 2013.

Abstract:

This paper presents a robust method for solving the map matching problem using massive GPS trace data. Map matching is the procedure of determining the path of a user on a map from a sequence of positions, called a trajectory. When the trajectory is sparse and noisy, the accuracy of matching a single trajectory is limited due to the large number of possible routes that can be inferred from trajectory samples. In this paper, we introduce a data-driven map matching method that aggregates information from multiple trajectories to improve the map matching result of each individual trajectory. The proposed approach is based on the observation that there exists regularity among common trajectories of human beings or vehicles. More precisely, among all possible k-segments (i.e., k consecutive edges on the road network), a typical trajectory collection only utilizes a small fraction of them. This motivates our data-driven map matching method, which optimizes the projected paths of the input trajectories so that the number of the k-segments being used is minimized. We present a formulation that admits efficient optimization via alternating optimization. We tested the algorithm on both synthesized and real datasets. Experimental results demonstrate that the proposed approach is superior to state-of-art single trajectory map matching algorithms in both settings. Moreover, we also show that the extracted popular k-segments can be used to process trajectories that are not present in the input trajectory set. This leads to a map matching algorithm that is as efficient as existing single trajectory map matching algorithms, but with much improved map matching quality.

Bibtex: 

@inproceedings{lhkzg-lsjmmgt-13,
  title = "Large-Scale Joint Map Matching of GPS Traces", 
  author = "Y. Li, Q. Huang, M. Kerber, L. Zhang and L. Guibas",
  booktitle = "Proc. 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.",
  year = 2013
}