A Novel Map Matching Algorithm

Abstract:

Presently, most of the researches on Map Matching focus on high sampling rate and accurate GPS points. This paper discusses a challenging problem with low GPS sampling rate and some continuous points with large deviation. To solve the problem efficiently, a novel matching method named F&PT is proposed. Firstly we employ a new method to generate sets of candidate roads. The GPS error analysis based on points is translated into based on roads. Secondly, a local strategy based on potential real trajectories is applied to solve the core problem of selecting an optimal road from the sets which contain only two candidate roads. In this approach, we consider not only the spatial location information and orientation angle information but also the influence of local points on the matching point from a new sight. We evaluate our method based on a real trajectory dataset. The experiments show that the proposed method has a higher accuracy compared with the related methods, e.g. ST-matching algorithm and IVMM algorithm, when the sampling interval is less than 210s.

• Periodical: Applied Mechanics and Materials (Volumes 556-562)
• Pages: 4139-4145
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.556-562.4139
• Online since: May 2014
• Authors: Guo Yong Cai*, Rui Lv, Li Yuan Wang, Hao Wu
• Keywords: GPS Trajectory, Large Deviation, Low Sampling Rate, Map Matching, Potential Real Trajectory

References

[1] Brakatsoulas S, Pfoser D, Tryfona N. Practical data management techniques for vehicle tracking data[C]/Data Engineering, 2005. ICDE 2005. Proceedings. 21st International Conference on. IEEE, 2005: 324-325.

DOI: 10.1109/icde.2005.109

[2] Lou Y, Zhang C, Zheng Y, et al. Map-matching for low-sampling-rate GPS trajectories[C]/Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2009: 352-361.

DOI: 10.1145/1653771.1653820

[3] Yuan J, Zheng Y, Zhang C, et al. An interactive-voting based map matching algorithm[C]/Mobile Data Management (MDM), 2010 Eleventh International Conference on. IEEE, 2010: 43-52.

DOI: 10.1109/mdm.2010.14

[4] Alt H, Efrat A, Rote G, et al. Matching planar maps[C]/Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2003: 589-598.

[5] Brakatsoulas S, Pfoser D, Salas R, et al. On map-matching vehicle tracking data[C]/Proceedings of the 31st international conference on Very large data bases. VLDB Endowment, 2005: 853-864.

[6] Civilis A, Jensen C S, Nenortaite J, et al. Efficient tracking of moving objects with precision guarantees[C]/Mobile and Ubiquitous Systems: Networking and Services, 2004. MOBIQUITOUS 2004. The First Annual International Conference on. IEEE, 2004: 164-173.

DOI: 10.1109/mobiq.2004.1331723

[7] Civilis A, Jensen C S, Pakalnis S. Techniques for efficient road- jo/wedyvc4 `rf4t52t Eleventh International Conference on. IEEE, 2010: 249-257.

[8] Miwa T, Kiuchi D, Yamamoto T, et al. Development of map matching algorithm for low frequency probe data[J]. Transportation Research Part C: Emerging Technologies, 2012, 22: 132-145.

DOI: 10.1016/j.trc.2012.01.005

[9] Hunter T, Abbeel P, Bayen A M. The path inference filter: model-based low-latency map matching of probe vehicle data[M]/Algorithmic Foundations of Robotics X. Springer Berlin Heidelberg, 2013: 591-607.

DOI: 10.1007/978-3-642-36279-8_36

[10] She X, He Z, Nie P, et al. Online Map-Matching Framework for Floating-Car Data with Low Sampling Rate in Urban Road Network[C]/Transportation Research Board 91st Annual Meeting. 2012 (12-1751).

DOI: 10.1049/iet-its.2011.0226

[11] White T. Hadoop: the definitive guide[M]. O'Reilly, (2012).