Incremental route inference from low-sampling GPS data: An opportunistic approach to online map matching

With the surging of smart device sensing and mobile networking, GPS data has been widely available for identifying vehicle position and route on the road map. For many real-time applications, such as traffic sensing and route recommendation, it is critical to immediately infer travelling route with incoming GPS data. In this paper, an opportunistic approach to online map matching is proposed to incrementally infer routes from low-sampling GPS data with low output latency. Unlike the hidden Markov model (HMM)-based approach, which often experiences certain delay between the GPS observation and inference, our algorithm can produce immediate inference when a new GPS point becomes available. Furthermore, a rollback mechanism is provided to correct the already inferred route when some abnormal situations are detected during the opportunistic inference process. We evaluate the proposed algorithm using real dataset of GPS trajectories over 100 cities around the world. Experimental results show that our algorithm is better than, or at least comparable to the state-of-the-art algorithms in terms of inference accuracy. More importantly, our algorithm can yield much shorter output latency and require less execution time, which is critical for many real-time navigation applications and location-based services.