Map matching: facts and myths

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.