Map Matching Algorithm: Empirical Review Based on Indian OpenStreetMap Road Network Data
Abstract: Locating devices on the road network is crucial for any location-based system. Accuracy of map matching algorithms may highly affect the accuracy of any location-based service. This paper includes an empirical review of five major map matching algorithms for locating a device on a digital road network. A standard dataset was used to simulate the working of map matching algorithms. After ascertaining the accuracy of map matching algorithms, it was tested on a real road network. Six different routes varying from 0.6 kilometers to 32 kilometers, covering a total distance of 82.2 kilometers were included in the experiment. Performance of map matching algorithms was evaluated on a total of 2094 road nodes with 1271070 Global Positioning System (GPS) points on the basis of matched, unmatched nodes with root mean square error. It was concluded that Hidden-Markov Model based map matching algorithms has reasonably good accuracy (96% using global data and 89% using Indian dataset) and execution time in comparison to geometric, topological, Kalman filter and Frechet distance based algorithms.
Keywords: Hidden markov model, kalman filter, frechet distance, OSM, GPS.
Received October 22, 2019; accepted June 8, 2021