{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:23Z","timestamp":1750220963493,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,8,12]],"date-time":"2019-08-12T00:00:00Z","timestamp":1565568000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>We examine the problem of computing shortest paths in a transportation network from a set of geographically clustered source nodes to a set of target nodes. Such many-to-many shortest path computations are an essential and computationally expensive part of many emerging applications that involve map matching of imprecise trajectories. Existing solutions to this problem mostly conform to the obvious approach of performing a single-source shortest path computation for each source node. We present an algorithm that exploits the clustered nature of the source nodes. Specifically, we rely on the observation that paths originating from a cluster of nodes typically exit the source region's boundary through a small number of nodes. Evaluations on a real road network show that the proposed algorithm provides a speed-up of several times over the conventional approach when the source nodes are densely clustered in a region. We also demonstrate that the presented technique is capable of substantially accelerating map matching of sparse and noisy trajectories.<\/jats:p>","DOI":"10.1145\/3329676","type":"journal-article","created":{"date-parts":[[2019,8,13]],"date-time":"2019-08-13T14:41:50Z","timestamp":1565707310000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast Computation of Clustered Many-to-many Shortest Paths and Its Application to Map Matching"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0166-0409","authenticated-orcid":false,"given":"George R.","family":"Jagadeesh","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thambipillai","family":"Srikanthan","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,8,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trb.2013.03.008"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.3141\/2413-07"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.200"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790248.2790257"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1972457.1972485"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666310.2666429"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITSC.2015.435"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653818"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2013.02.002"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.trc.2012.08.001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2013.2282352"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITSC.2015.411"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653820"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424430"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791188.2791192"},{"volume-title":"The Shortest Path Problem: 9th DIMACS Implementation Challenge","author":"Hilger Moritz","key":"e_1_2_1_17_1","unstructured":"Moritz Hilger , Ekkehard K\u00f6hler , Rolf H. M\u00f6hring , and Heiko Schilling . 2009. Fast point-to-point shortest path computations with arc-flags . In The Shortest Path Problem: 9th DIMACS Implementation Challenge . American Mathematical Society , 41--72. Moritz Hilger, Ekkehard K\u00f6hler, Rolf H. M\u00f6hring, and Heiko Schilling. 2009. Fast point-to-point shortest path computations with arc-flags. In The Shortest Path Problem: 9th DIMACS Implementation Challenge. American Mathematical Society, 41--72."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"key":"e_1_2_1_19_1","volume-title":"Werneck","author":"Bast Hannah","year":"2016","unstructured":"Hannah Bast , Daniel Delling , Andrew V. Goldberg , Matthias M\u00fcller-Hannemann , Thomas Pajor , Peter Sanders , Dorothea Wagner , and Renato F . Werneck . 2016 . Route planning in transportation networks. In Algorithm Engineering. Springer International Publishing , 19--80. Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias M\u00fcller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. 2016. Route planning in transportation networks. In Algorithm Engineering. Springer International Publishing, 19--80."},{"key":"e_1_2_1_20_1","volume-title":"Werneck","author":"Delling Daniel","year":"2011","unstructured":"Daniel Delling , Andrew V. Goldberg , and Renato F . Werneck . 2011 . Faster batched shortest paths in road networks. OASIcs-OpenAccess Series in Informatics , 20. Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2011. Faster batched shortest paths in road networks. OASIcs-OpenAccess Series in Informatics, 20."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384251"},{"key":"e_1_2_1_22_1","unstructured":"Sebastian Knopp. 2006. Efficient Computation of Many-to-many Shortest Paths. Diplomarbeit Universit\u00e4t Karlsruhe.  Sebastian Knopp. 2006. Efficient Computation of Many-to-many Shortest Paths. Diplomarbeit Universit\u00e4t Karlsruhe."},{"key":"e_1_2_1_23_1","volume-title":"Goldberg and Chris Harrelson","author":"Andrew","year":"2005","unstructured":"Andrew V. Goldberg and Chris Harrelson . 2005 . Computing the shortest path: A search meets graph theory. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms. 156--165. Andrew V. Goldberg and Chris Harrelson. 2005. Computing the shortest path: A search meets graph theory. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms. 156--165."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITSC.2015.465"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2017.1400548"},{"key":"e_1_2_1_26_1","volume-title":"Orlin","author":"Ahuja Ravindra K.","year":"1993","unstructured":"Ravindra K. Ahuja , Thomas L. Magnanti , and James B . Orlin . 1993 . Network flows: Theory, Algorithms, and Applications. Prentice-Hall , Inc. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993. Network flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644038.1644048"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITSC.2012.6338627"},{"key":"e_1_2_1_30_1","volume-title":"Map matching based on conditional random fields and route preference mining for uncertain trajectories. Mathematical Problems in Engineering","author":"Xu Ming","year":"2015","unstructured":"Ming Xu , Yiman Du , Jianping Wu , and Yang Zhou . 2015. Map matching based on conditional random fields and route preference mining for uncertain trajectories. Mathematical Problems in Engineering 2015 , Article 717095. Ming Xu, Yiman Du, Jianping Wu, and Yang Zhou. 2015. Map matching based on conditional random fields and route preference mining for uncertain trajectories. Mathematical Problems in Engineering 2015, Article 717095."},{"volume-title":"Progress in Location-Based Services","author":"Yang Jian","key":"e_1_2_1_31_1","unstructured":"Jian Yang and Liqiu Meng . 2015. Feature selection in conditional random fields for map matching of GPS trajectories . In Progress in Location-Based Services . Springer International Publishing , 121--135. Jian Yang and Liqiu Meng. 2015. Feature selection in conditional random fields for map matching of GPS trajectories. In Progress in Location-Based Services. Springer International Publishing, 121--135."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2017.2647967"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3329676","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3329676","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:18Z","timestamp":1750204458000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3329676"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,12]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3329676"],"URL":"https:\/\/doi.org\/10.1145\/3329676","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2019,8,12]]},"assertion":[{"value":"2017-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}