Map matching
Authors:
Open Access
- 5 November 2013
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 484-487
Abstract
Hidden Markov Models (HMMs) based map matching - that matches a sequence of location samples to a road network - has received a lot of traction in recent years. In this paper we revisit the basic assumption underlying HMM-based map matching algorithms, namely, the hypothesis that the true mobility is Markovian. We use the Chapman-Kolmogorov test and argue that mobility is non-Markovian (especially when the moving object has an intent to reach a specific destination) using thousands of real taxicab mobility datasets spanning several weeks. Based on these observations we present an alternate approach to the map matching problem that relies exclusively on shortest path computations, which are at most linear in the number of road segments, and thus avoids expensive complexity of HMM-based map matching algorithms (e.g., using a Viterbi decoder). We present extensive experimental results to show that our approach vastly outperforms HMM-based approaches in terms of both computational complexity and accuracy.Keywords
Funding Information
- U.S. Army Research Laboratory (W911NF-09-2-0053)
This publication has 6 references indexed in Scilit:
- EnAcq2011
- VTrack2009
- Hidden Markov map matching through noise and sparseness2009
- A Markov Model for Driver Turn PredictionSAE International Journal of Advances and Current Practices in Mobility, 2008
- Map Matching with Travel Time ConstraintsSAE International Journal of Advances and Current Practices in Mobility, 2007
- Markov Chains1997