An efficient algorithm for mapping vehicle trajectories onto road networks

Modern mobile technology has enabled the collection of large scale vehicle trajectories using GPS devices. As GPS measurements may come with error, vehicle trajectories are often noisy. A common practice to alleviate this issue is to apply map-matching, i.e., to align vehicle trajectories with the road segments in a digitized road network. This paper presents an efficient solution for map-matching problem that won the SIGSPATIAL CUP 2012. Given a road network, our solution first constructs a gird index on the road segments. For each point p on a vehicle trajectory, we employ the index to identify a candidate set of road segments that are close to p, and then we refine the candidate set to select a segment that matches p with the highest probability. The selection of the best match is based on a metric that takes into account (i) the correlation between consecutive GPS measurements as well as (ii) the directions and shapes of the road segments. Experimental results on real vehicle trajectories and road networks demonstrate the effectiveness and efficiency of the proposed solution