{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,19]],"date-time":"2025-10-19T06:07:22Z","timestamp":1760854042181,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,6,30]],"date-time":"2018-06-30T00:00:00Z","timestamp":1530316800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National University of Singapore (Suzhou) Research Institute, 377 Lin Quan Street, Suzhou Industrial Park, Jiang Su, People's Republic of China","award":["215123"],"award-info":[{"award-number":["215123"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61472266"],"award-info":[{"award-number":["61472266"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2018,6,30]]},"abstract":"<jats:p>With the increasing availability of GPS-equipped mobile devices, location-based services have become an integral part of everyday life. Among one of the initial steps of positioning data management, map matching aims to reduce the uncertainty in a trajectory by matching the GPS points to the road network on a digital map. Most existing work has focused on estimating the likelihood of a candidate route based on the GPS observations, while neglecting to model the probability of a route choice from the perspective of drivers. In this work, we propose a novel feature-based map matching algorithm that estimates the cost of a candidate route based on both GPS observations and human factors. To take human factors into consideration is highly important, especially when dealing with low sampling rate data where most of the movement details are lost. Additionally, we simultaneously analyze a subsequence of coherent GPS points by utilizing a new segment-based probabilistic map matching strategy, which is less susceptible to the noisiness of the positioning data. We have evaluated both the offline and the online versions of our proposed approach on a public large-scale GPS dataset, which consists of 100 trajectories distributed all over the world. The experimental results show that our method is robust to sparse data with large sampling intervals (e.g., 60s \u223c 300s) and challenging track features (e.g., u-turns and loops). Measurements including map matching accuracy and system efficiency have been thoroughly evaluated and discussed. Compared with two state-of-the-art map matching algorithms, our method substantially reduces the route mismatch error by 6.4% \u223c 32.3% (either offline or online with the window size set to 360s), with a slight increase in terms of the processing time. The experimental results show that our proposed method obtains the state-of-the-art map matching results in all the different combinations of sampling rates and challenging features.<\/jats:p>","DOI":"10.1145\/3223049","type":"journal-article","created":{"date-parts":[[2018,8,13]],"date-time":"2018-08-13T12:29:41Z","timestamp":1534163381000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Feature-based Map Matching for Low-Sampling-Rate GPS Trajectories"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6525-6133","authenticated-orcid":false,"given":"Yifang","family":"Yin","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajiv Ratn","family":"Shah","sequence":"additional","affiliation":[{"name":"Indraprastha Institute of Information Technology Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guanfeng","family":"Wang","sequence":"additional","affiliation":[{"name":"Grab Research and Development, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roger","family":"Zimmermann","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,8,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3046945"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2016.2645150"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820783.2820824"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Conference on Very Large Data gases (VLDB\u201905)","author":"Brakatsoulas Sotiris","year":"2005","unstructured":"Sotiris Brakatsoulas , Dieter Pfoser , Randall Salas , and Carola Wenk . 2005 . On map-matching vehicle tracking data . In Proceedings of the Conference on Very Large Data gases (VLDB\u201905) . 853--864. Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. 2005. On map-matching vehicle tracking data. In Proceedings of the Conference on Very Large Data gases (VLDB\u201905). 853--864."},{"key":"e_1_2_1_5_1","first-page":"33","article-title":"Segmenting trajectories: A framework and algorithms using spatiotemporal criteria","volume":"2011","author":"Buchin Maike","year":"2011","unstructured":"Maike Buchin , Anne Driemel , Marc van Kreveld , and Vera Sacrist\u00e1n . 2011 . Segmenting trajectories: A framework and algorithms using spatiotemporal criteria . J. Spatial Info. Sci. 2011 , 3 (2011), 33 -- 63 . Maike Buchin, Anne Driemel, Marc van Kreveld, and Vera Sacrist\u00e1n. 2011. Segmenting trajectories: A framework and algorithms using spatiotemporal criteria. J. Spatial Info. Sci. 2011, 3 (2011), 33--63.","journal-title":"J. Spatial Info. Sci."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IVS.2007.4290280"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2093973.2094004"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2845080"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"C. Y. Goh J. Dauwels N. Mitrovic M. T. Asif A. Oran and P. Jaillet. 2012. Online map-matching based on hidden Markov model for real-time traffic sensing applications. In IEEE Intell. Transport. Syst. 776--781.  C. Y. Goh J. Dauwels N. Mitrovic M. T. Asif A. Oran and P. Jaillet. 2012. Online map-matching based on hidden Markov model for real-time traffic sensing applications. In IEEE Intell. Transport. Syst. 776--781.","DOI":"10.1109\/ITSC.2012.6338627"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Transportation Research Board Annual Meeting.","author":"Greenfeld Joshua S.","year":"2002","unstructured":"Joshua S. Greenfeld . 2002 . Matching GPS observations to locations on a digital map . In Proceedings of the Transportation Research Board Annual Meeting. Joshua S. Greenfeld. 2002. Matching GPS observations to locations on a digital map. In Proceedings of the Transportation Research Board Annual Meeting."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/78.978396"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786756"},{"volume-title":"Proceedings of the IEEE Intelligent Vehicles Symposium. 1088--1093","author":"Kubi\u010dka M.","key":"e_1_2_1_14_1","unstructured":"M. Kubi\u010dka , A. Cela , P. Moulin , H. Mounier , and S. I. Niculescu . 2015. Dataset for testing and training of map-matching algorithms . In Proceedings of the IEEE Intelligent Vehicles Symposium. 1088--1093 . M. Kubi\u010dka, A. Cela, P. Moulin, H. Mounier, and S. I. Niculescu. 2015. Dataset for testing and training of map-matching algorithms. In Proceedings of the IEEE Intelligent Vehicles Symposium. 1088--1093."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666310.2666409"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.01.006"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424429"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13638-017-0814-6"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536221"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653820"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653818"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI\u201913)","author":"Osogami Takayuki","year":"2013","unstructured":"Takayuki Osogami and Rudy Raymond . 2013 . Map matching with inverse reinforcement learning . In Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI\u201913) . 2547--2553. Takayuki Osogami and Rudy Raymond. 2013. Map matching with inverse reinforcement learning. In Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI\u201913). 2547--2553."},{"volume-title":"11th International IEEE Conference on Intelligent Transportation Systems. 862--867","author":"Pink O.","key":"e_1_2_1_23_1","unstructured":"O. Pink and B. Hummel . 2008. A statistical approach to map matching using road network geometry, topology and vehicular motion constraints . In 11th International IEEE Conference on Intelligent Transportation Systems. 862--867 . O. Pink and B. Hummel. 2008. A statistical approach to map matching using road network geometry, topology and vehicular motion constraints. In 11th International IEEE Conference on Intelligent Transportation Systems. 862--867."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10291-003-0069-z"},{"key":"e_1_2_1_25_1","volume-title":"Ochieng","author":"Quddus Mohammed A.","year":"2006","unstructured":"Mohammed A. Quddus , Robert B. Noland , and Washington Y . Ochieng . 2006 . A high accuracy fuzzy logic based map matching algorithm for road transport. J. Intell. Transport. Syst . (2006), 103--115. Mohammed A. Quddus, Robert B. Noland, and Washington Y. Ochieng. 2006. A high accuracy fuzzy logic based map matching algorithm for road transport. J. Intell. Transport. Syst. (2006), 103--115."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-014-0208-4"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732940"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74126-8_23"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Conference on Networked Systems Design and Implementation. 267--280","author":"Thiagarajan Arvind","year":"2011","unstructured":"Arvind Thiagarajan , Lenin Ravindranath , Hari Balakrishnan , Samuel Madden , and Lewis Girod . 2011 . Accurate, low-energy trajectory mapping for mobile devices . In Proceedings of the Conference on Networked Systems Design and Implementation. 267--280 . Arvind Thiagarajan, Lenin Ravindranath, Hari Balakrishnan, Samuel Madden, and Lewis Girod. 2011. Accurate, low-energy trajectory mapping for mobile devices. In Proceedings of the Conference on Networked Systems Design and Implementation. 267--280."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644038.1644048"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424411"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424392"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666310.2666383"},{"key":"e_1_2_1_34_1","volume-title":"Kornhauser","author":"White Christopher E.","year":"2000","unstructured":"Christopher E. White , David Bernstein , and Alain L . Kornhauser . 2000 . Some map matching algorithms for personal navigation assistants. Transport. Res. Part C: Emerg. Technol . (2000), 91--108. Christopher E. White, David Bernstein, and Alain L. Kornhauser. 2000. Some map matching algorithms for personal navigation assistants. Transport. Res. Part C: Emerg. Technol. (2000), 91--108."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2700287"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996913.2997015"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2671188.2749354"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869807"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2010.14"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.42"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2743025"},{"volume-title":"Proceedings of the Innovative Applications of Artificial Intelligence Conference (AAAI\u201908)","author":"Ziebart Brian D.","key":"e_1_2_1_42_1","unstructured":"Brian D. Ziebart , Andrew L. Maas , J. Andrew Bagnell , and Anind K. Dey . 2008. Maximum entropy inverse reinforcement learning . In Proceedings of the Innovative Applications of Artificial Intelligence Conference (AAAI\u201908) . 1433--1438. Brian D. Ziebart, Andrew L. Maas, J. Andrew Bagnell, and Anind K. Dey. 2008. Maximum entropy inverse reinforcement learning. In Proceedings of the Innovative Applications of Artificial Intelligence Conference (AAAI\u201908). 1433--1438."}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3223049","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3223049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:05Z","timestamp":1750210745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3223049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,30]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6,30]]}},"alternative-id":["10.1145\/3223049"],"URL":"https:\/\/doi.org\/10.1145\/3223049","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2018,6,30]]},"assertion":[{"value":"2017-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}