{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:11:26Z","timestamp":1761293486245,"version":"build-2065373602"},"reference-count":39,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2016,11,10]],"date-time":"2016-11-10T00:00:00Z","timestamp":1478736000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Location-aware devices can be used to record the positions of moving objects for further spatio-temporal data analysis. For instance, we can analyze the routes followed by a person or a group of people, to discover hidden patterns in trajectory data. Typically, the positions of moving objects are registered by GPS devices, and most of the time, the recorded positions do not match the road actually followed by the object carrying the device, due to different sources of errors. Thus, matching the moving object\u2019s actual position to a location on a digital map is required. The problem of matching GPS-recorded positions to a road network is called map matching (MM). Although many algorithms have been proposed to solve this problem, few of them consider the uncertainty caused by the absence of information about the moving object\u2019s position in-between consecutive recorded locations. In this paper, we study the relationship between map matching and uncertainty, and we propose a novel MM algorithm that uses space-time prisms in combination with weighted k-shortest path algorithms. We applied our algorithm to real-world cases and to computer-generated trajectory samples with a variety of properties. We compare our results against a number of well-known algorithms that we have also implemented and show that it outperforms existing algorithms, allowing us to obtain better matches, with a negligible loss in performance. In addition, we propose a novel accuracy measure that allows a better comparison between different MM algorithms. We applied this novel measure to compare our algorithm against existing algorithms.<\/jats:p>","DOI":"10.3390\/ijgi5110204","type":"journal-article","created":{"date-parts":[[2016,11,10]],"date-time":"2016-11-10T10:51:39Z","timestamp":1478775099000},"page":"204","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Uncertainty-Based Map Matching: The Space-Time Prism and k-Shortest Path Algorithm"],"prefix":"10.3390","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5774-0948","authenticated-orcid":false,"given":"Bart","family":"Kuijpers","sequence":"first","affiliation":[{"name":"UHasselt\u2013Hasselt University and transnational University Limburg, Databases and Theoretical Computer Science Research Group, Agoralaan, Diepenbeek 3590, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bart","family":"Moelans","sequence":"additional","affiliation":[{"name":"UHasselt\u2013Hasselt University and transnational University Limburg, Databases and Theoretical Computer Science Research Group, Agoralaan, Diepenbeek 3590, Belgium"},{"name":"VikingCo, Hasselt 3500, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Walied","family":"Othman","sequence":"additional","affiliation":[{"name":"UHasselt\u2013Hasselt University and transnational University Limburg, Databases and Theoretical Computer Science Research Group, Agoralaan, Diepenbeek 3590, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3945-4187","authenticated-orcid":false,"given":"Alejandro","family":"Vaisman","sequence":"additional","affiliation":[{"name":"Instituto Tecnol\u00f3gico de Buenos Aires 1106, Argentina"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2016,11,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Giannotti, F., and Pedreschi, D. (2008). Mobility, Data Mining and Privacy\u2014Geographic Knowledge Discovery, Springer.","DOI":"10.1007\/978-3-540-75177-9"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0968-090X(00)00026-7","article-title":"Some map matching algorithms for personal navigation assistants","volume":"8","author":"White","year":"2000","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_3","unstructured":"G\u00fcting, R.H., and Schneider, M. (2005). Moving Objects Databases, Morgan Kaufmann."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1145\/321707.321712","article-title":"Finding the lengths of all shortest paths in N-node nonnegative-distance complete networks using \n      \n        \n          \n            \n\t\t\t  1\n\t\t\t  2\n            \n          \n        \n      \n      N3 additions and N3 comparisons","volume":"19","author":"Yen","year":"1972","journal-title":"J. ACM"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.compenvurbsys.2014.07.009","article-title":"A critical review of real-time map-matching algorithms: Current issues and future directions","volume":"48","author":"Hashemi","year":"2014","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_6","unstructured":"Bernstein, D., and Kornhauser, A.L. (1998). An Introduction to Map Matching for Personal Navigation Assistans, Transportation Research Board. Technical Report."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1315","DOI":"10.1038\/nbt1004-1315","article-title":"What is a hidden Markov model?","volume":"22","author":"Eddy","year":"2004","journal-title":"Nat. Biotechnol."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Newson, P., and Krumm, J. (2009, January 4\u20136). Hidden Markov map matching through noise and sparseness. Proceedings of the 17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, New York, NY, USA.","DOI":"10.1145\/1653771.1653818"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Krumm, J., Letchner, J., and Horvitz, E. (2007, January 3\u20136). Map matching with travel time constraints. Proceedings of the Society of Automotive Engineers (SAE) 2007 World Congress, Detroit, MI, USA.","DOI":"10.4271\/2007-01-1102"},{"key":"ref_10","unstructured":"Greenfeld, J.S. (2002, January 13\u201317). Matching GPS observations to locations on a digital map. Proceedings of the Transportation Research Board 81st Annual Meeting, Washington, DC, USA."},{"key":"ref_11","unstructured":"Brakatsoulas, S., Pfoser, D., Salas, R., and Wenk, C. (September, January 31). On map-matching vehicle tracking data. Proceedings of the 31st International Conference on Very Large Data Bases, Toronto, ON, Canada."},{"key":"ref_12","unstructured":"Wenk, C., Salas, R., and Pfoser, D. (2006, January 3\u20135). Addressing the need for map-matching speed: Localizing global curve-matching algorithms. Proceedings of the 18th International Conference on Scientific and Statistical Database Management, Vienna, Austria."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1115\/1.3662552","article-title":"A new approach to linear filtering and prediction problems","volume":"82","author":"Kalman","year":"1960","journal-title":"Trans. ASME J. Basic Eng."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1017\/S0373463303002212","article-title":"An extended Kalman Filter algorithm for integrating GPS and low-cost dead reckoning system data for vehicle performance and emissions monitoring","volume":"56","author":"Quddus","year":"2003","journal-title":"J. Navig."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.trc.2013.07.009","article-title":"High accuracy tightly-coupled integrity monitorin algorithm for map matching","volume":"36","author":"Li","year":"2013","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_16","first-page":"1","article-title":"Map matching in complex urban road networks","volume":"55","author":"Quddus","year":"2003","journal-title":"Braz. Jm Cartogr. Revista Brasil. Cartogr."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1016\/S0019-9958(65)90241-X","article-title":"Fuzzy sets","volume":"8","author":"Zadeh","year":"1965","journal-title":"Inf. Control"},{"key":"ref_18","unstructured":"Zhao, Y. (1997). Vehicle Location and Navigation Systems: Intelligent Transportation Systems, Navtech Seminars and GPS Supply."},{"key":"ref_19","unstructured":"Syed, S., and Cannon, M.E. (2004, January 26\u201328). Fuzzy logic based map matching algorithm for vehicle navigation system in urban canyons. Proceedings of the 2004 National Technical Meeting of the Institute of Navigation, Monterey, CA, USA."},{"key":"ref_20","unstructured":"Quddus, M.A. (2006). High Integrity Map Matching Algorithms for Advanced Transport Telematics Applications. [Ph.D. Thesis, Imperial College]."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., and Huang, Y. (2009, January 4\u20136). Map-matching for low-sampling-rate GPS trajectories. Proceedings of the 17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, Seattle, WA, USA.","DOI":"10.1145\/1653771.1653820"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Li, Y., Huang, Q., Kerber, M., Zhang, L., and Guibas, L. (2013, January 5\u20138). Large-scale joint map matching of GPS traces. Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, New York, NY, USA.","DOI":"10.1145\/2525314.2525333"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/j.trc.2015.08.014","article-title":"Estimating the most likely space\u2013time paths, dwell times and path uncertainties from vehicle trajectory data: A time geographic method","volume":"66","author":"Tang","year":"2016","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1080\/13658816.2013.816427","article-title":"Map-matching algorithm for large-scale low-frequency floating car data","volume":"28","author":"Chen","year":"2014","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1080\/15472450.2011.570103","article-title":"Large-scale freeway network traffic monitoring: A map-matching algorithm based on low-logging frequency GPS probe data","volume":"15","author":"Wang","year":"2011","journal-title":"J. Intell. Transp. Syst."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.trc.2012.01.005","article-title":"Development of map matching algorithm for low frequency probe data","volume":"22","author":"Miwa","year":"2016","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.trc.2013.02.002","article-title":"Path inference from sparse floating car data for urban networks","volume":"30","author":"Rahmani","year":"2013","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1109\/TITS.2013.2282352","article-title":"The path inference filter: Model-based low-latency map matching of probe vehicle data","volume":"15","author":"Hunter","year":"2014","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1080\/13658816.2015.1086922","article-title":"Curvedness feature constrained map matching for low-frequency probe vehicle data","volume":"30","author":"Zeng","year":"2016","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_30","unstructured":"G\u00fcting, R.H., Papadias, D., and Lochovsky, F.H. (1999). Lecture Notes in Computer Science, Springer."},{"key":"ref_31","unstructured":"Bertino, E., and Floriani, L.D. (2003). SpadaGIS, Workshop on Spatial Data and Geographic Information Systems, University of Genova."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1023\/A:1015812206586","article-title":"Modeling moving objects over multiple granularities","volume":"36","author":"Hornsby","year":"2002","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_33","unstructured":"Halevy, A.Y., and Gal, A. (2002). Lecture Notes in Computer Science, Springer."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1111\/j.1435-5597.1970.tb01464.x","article-title":"What about people in regional science?","volume":"24","year":"1970","journal-title":"Papers Reg. Sci. Assoc."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1111\/j.1538-4632.2005.00575.x","article-title":"A measurement theory for time geography","volume":"37","author":"Miller","year":"2005","journal-title":"Geogr.l Anal."},{"key":"ref_36","unstructured":"Othman, W. (2009). Uncertainty Management in Trajectory Databases. [Ph.D. Thesis, Hasselt University]."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A nnte on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Ghys, K., Kuijpers, B., Moelans, B., Othman, W., Vangoidsenhoven, D., and Vaisman, A.A. (2009, January 4\u20136). Map matching and uncertainty: An algorithm and real-world experiments. Proceedings of the 17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, Seattle, DC, USA.","DOI":"10.1145\/1653771.1653846"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/5\/11\/204\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:35:14Z","timestamp":1760211314000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/5\/11\/204"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,10]]},"references-count":39,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2016,11]]}},"alternative-id":["ijgi5110204"],"URL":"https:\/\/doi.org\/10.3390\/ijgi5110204","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2016,11,10]]}}}