Please use this identifier to cite or link to this item:
Title: Fast computation of clustered many-to-many shortest paths and its application to map matching
Authors: Jagadeesh, George Rosario
Srikanthan, Thambipillai
Keywords: Engineering::Computer science and engineering
Issue Date: 2019
Source: Jagadeesh, 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/3329676
Journal: ACM Transactions on Spatial Algorithms and Systems
Abstract: 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.
ISSN: 2374-0353
DOI: 10.1145/3329676
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).
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
J19.pdf1.75 MBAdobe PDFThumbnail

Citations 50

Updated on Mar 14, 2023

Web of ScienceTM
Citations 50

Updated on Mar 21, 2023

Page view(s)

Updated on Mar 22, 2023

Download(s) 50

Updated on Mar 22, 2023

Google ScholarTM




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