Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorJagadeesh, George Rosarioen_US
dc.contributor.authorSrikanthan, Thambipillaien_US
dc.identifier.citationJagadeesh, G. R., & Srikanthan, T. (2019). Fast computation of clustered many-to-many shortest paths and its application to map matching. ACM Transactions on Spatial Algorithms and Systems, 5(3). doi:10.1145/3329676en_US
dc.description.abstractWe 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.en_US
dc.relation.ispartofACM Transactions on Spatial Algorithms and Systemsen_US
dc.rights© 2019 Association for Computing Machinery (ACM). All rights reserved. This paper was published in ACM Transactions on Spatial Algorithms and Systems and is made available with permission of Association for Computing Machinery (ACM).en_US
dc.subjectEngineering::Computer science and engineeringen_US
dc.titleFast computation of clustered many-to-many shortest paths and its application to map matchingen_US
dc.typeJournal Articleen
dc.contributor.schoolSchool of Computer Science and Engineeringen_US
dc.description.versionAccepted versionen_US
dc.subject.keywordsMap Matchingen_US
dc.subject.keywordsSpeed-up Techniqueen_US
item.fulltextWith Fulltext-
Appears in Collections:SCSE Journal Articles
Files in This Item:
File Description SizeFormat 
J19.pdf1.75 MBAdobe PDFThumbnail

Citations 50

Updated on Mar 23, 2023

Web of ScienceTM
Citations 50

Updated on Mar 21, 2023

Page view(s)

Updated on Mar 24, 2023

Download(s) 50

Updated on Mar 24, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.