Capturing Spatial Relationship Mapping Patterns between GPS Coordinates and Road Network Using Machine Learning and Partitioning Techniques
Article Sidebar
Main Article Content
Abstract
Map matching is a technique used to identify which path a vehicle is travelling on in a road map. Since it is a crucial fundamental step for a wide range of transportation applications, many map-matching algorithms have been devised ranging from simple geometric calculation methods to more sophisticated methods. However, the study of spatial relationship patterns between GPS coordinates and road segments mapped with map-matching has not received enough attention from researchers. This paper presents a framework, called Proxy Map Matching (PMM), to learn such patterns using machine learning techniques. However, we find that solely employing machine learning techniques on such data is not sufficient to capture the patterns. Solving this problem that way results in an inaccurate proxy model. In PMM, we construct several proxy map matchers and assign them to each group of data based on their spatial proximity, thereby achieving accuracy improvement. An experiment on real-world data shows that the framework achieves above 85% accuracy with integration of machine learning techniques, and outperforms the methods which solely employ machine learning techniques significantly. Moreover, the proposed proxy model can perform very fast matching. For 14,177 GPS coordinate pairs per second, we achieve 88.4% accuracy.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
D. Bernstein and A. Kornhauser, “An introduction to map matching for personal navigation assistants,” New Jersey TIDE Center Technical Report, 1996.
Q. Huang, Y. Yang, Y. Xu, F. Yang, Z. Yuan and Y. Sun, “Citywide road-network traffic monitoring using large-scale mobile signaling data,”Neurocomputing, 2021.
Z. Wang, M. Lu, X. Yuan, J. Zhang and H. Van De Wetering, “Visual traffic jam analysis based on trajectory data,” IEEE Transactions on Visualization and Computer Graphics, vol. 19, no. 12, pp. 2159–2168, 2013.
T. Boonchoo, X. Ao, and Q. He, “Multiaspect embedding for attribute-aware trajectories,” Symmetry, vol. 11, p. 1149, 09 2019.
M. Kubicka, A. Cela, H. Mounier and S. Niculescu, “Comparative study and applicationoriented classification of vehicular map-matching methods,” IEEE Intelligent Transportation Systems Magazine, vol. 10, pp. 150–166, Summer 2018.
N. Podevijn, J. Trogh, M. Aernouts, R. Berkvens, L. Martens, M. Weyn, W. Joseph and D. Plets, “Lorawan geo-tracking using map matching and compass sensor fusion,” Sensors, vol. 20, no. 20, 2020.
L. d. C. Gomes and L. H. M. K. Costa, “Vehicular dead reckoning based on machine learning and map matching,” in 2020 IEEE 92nd Vehicular Technology Conference (VTC2020-Fall), pp. 1–5, 2020.
D. Pfoser and C. S. Jensen, “Capturing the uncertainty of moving-object representations,” Advances in Spatial Databases Lecture Notes in Computer Science, vol. 1651, pp. 111–131, 1999.
Youjing Cui and Shuzhi Sam Ge, “Autonomous vehicle positioning with gps in urban canyon environments,” IEEE Transactions on Robotics and Automation, vol. 19, pp. 15–25, Feb 2003.
Y. Wang, Y. Zhu, Z. He, Y. Yue, and Q. Li, “Challenges and opportunities in exploiting large-scale gps probe data,” in HP Laboratories, Technical Report HPL-2011-109, 07 2011.
Y.-L. Hsueh and H.-C. Chen, “Map matching for low-sampling-rate gps trajectories by exploring real-time moving directions,” Information Sciences, vol. 433-434, pp. 55–69, 2018.
K. Zheng, Y. Zheng, X. Xie, and X. Zhou, “Reducing uncertainty of low-sampling-rate trajectories,” in 2012 IEEE 28th International Conference on Data Engineering, pp. 1144–1155, 2012.
M. A. Quddus, W. Y. Ochieng, and R. B. Noland, “Current map-matching algorithms for transport applications: State-of-the art and future research directions,” Transportation Research Part C: Emerging Technologies, vol. 15,no. 5, pp. 312 – 328, 2007.
M. Hashemi and H. A. Karimi, “A critical review of real-time map-matching algorithms: Current issues and future directions,” Computers, Environment and Urban Systems, vol. 48, pp. 153–165, 2014.
M. Hashemi, “Reusability of the output of map-matching algorithms across space and time through machine learning,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, pp. 3017–3026, Nov 2017.
C. Goh, J. Dauwels, N. Mitrovic, M. T. Asif, A. Oran, and P. Jaillet, “Online map-matching based on hidden markov model for real-time traffic sensing applications,” in 2012 15th International IEEE Conference on Intelligent Transportation Systems, pp. 776–781, 2012.
S. Taguchi, S. Koide, and T. Yoshimura, “Online map matching with route prediction,” IEEE Transactions on Intelligent Transportation Systems, vol. 20, no. 1, pp. 338–347, 2019
L. Luo, X. Hou, W. Cai, and B. Guo, “Incremental route inference from low-sampling gps data: An opportunistic approach to online map matching,” Information Sciences, vol. 512, pp. 1407–1423, 2020.
P. Chao, Y. Xu, W. Hua, and X. Zhou, “A sur- vey on map-matching algorithms,” in Databases Theory and Applications (R. Borovica-Gajic, J. Qi, and W. Wang, eds.), (Cham), pp. 121–133, Springer International Publishing, 2020.
C. Yang and G. Gid ́ofalvi, “Fast map matching, an algorithm integrating hidden markov model with precomputation,” International Journal of Geographical Information Science, vol. 32, no. 3, pp. 547–570, 2018.
P. Newson and J. Krumm, “Hidden markov map matching through noise and sparseness,” in Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS’09, (New York, NY, USA), pp. 336–343, ACM, 2009.
D. Zhang, Y. Dong, and Z. Guo, “A turning point-based offline map matching algorithm for urban road networks,” Information Sciences, vol. 565, pp. 32–45, 2021.
M. R. Gupta, S. Bengio, and J. Weston, “Training highly multiclass classifiers,” J. Mach. Learn. Res., vol. 15, p. 1461–1492, Jan. 2014
J. Kim, “Node based map matching algorithm for car navigation system,” in International Symposium on Automotive Technology Automation Global Deployment of Advanced Transportation Telematics/its, 1996.
C. E. White, D. Bernstein, and A. L. Kornhauser, “Some map matching algorithms for personal navigation assistants,” Transportation Research Part C: Emerging Technologies, vol. 8, no. 1, pp. 91–108, 2000.
J. S. Greenfeld, “Matching gps observations to locations on a digital map,” in Transportation Research Board. Meeting, National Research Council, (Washington, DC, USA), 2002
S. Brakatsoulas, D. Pfoser, R. Salas and C. Wenk, “On map-matching vehicle track- ing data,” in Proceedings of the 31st International Conference on Very Large Data Bases, VLDB’05, pp. 853–864, VLDB Endowment, 2005.
H. Alt, A. Efrat, G. Rote, and C. Wenk, “Matching planar maps,” Journal of Algorithms, vol. 49, no. 2, pp. 262–283, 2003.
C. Wenk, R. Salas, and D. Pfoser, “Addressing the need for map-matching speed: Localizing global curve-matching algorithms,” in 18th International Conference on Scientific and Statistical Database Management (SSDBM’06), pp. 379–388, July 2006.
B. Hummel, “Map matching for vehicle guidance,” Dynamic and Mobile GIS: Investigating Space and Time, 2006
J. Krumm, E. Horvitz, and J. Letchner, “Map matching with travel time constraints,” in SAE Technical Paper, SAE International, 2007.
Z. Shen, W. Du, X. Zhao, and J. Zou, “Dmm:Fast map matching for cellular data,” in Proceedings of the 26th Annual International Conference on Mobile Computing and Networking, MobiCom ’20, (New York, NY, USA), Association for Computing Machinery, 2020.
C. M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics). Berlin, Heidelberg: Springer-Verlag, 2006.
“Porto taxi database.” https://www. kaggle.com/c/pkdd-15-predict-taxi -service-trajectory-i/data, 2015. Accessed: 2022-05-31.
OpenStreetMap, “Open street map.” www. openstreetmap.org. Accessed: 2022-05-31.
“Taxi service challenge, trajectory prediction ecml-pkdd 2015.”https://archive.ics.uci.edu/ml/datasets/ Taxi+Service+Trajectory+-+Prediction+ Challenge,+ECML+PKDD+2015, 2015. Accessed: 2022- 05-31