Fast computation of clustered many-to-many shortest paths and its application to map matching
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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/145630 |
| _version_ | 1824454045683679232 |
|---|---|
| author | Jagadeesh, George Rosario Srikanthan, Thambipillai |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Jagadeesh, George Rosario Srikanthan, Thambipillai |
| author_sort | Jagadeesh, George Rosario |
| collection | NTU |
| description | 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. |
| first_indexed | 2025-02-19T03:16:04Z |
| format | Journal Article |
| id | ntu-10356/145630 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T03:16:04Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | ntu-10356/1456302020-12-30T06:58:44Z Fast computation of clustered many-to-many shortest paths and its application to map matching Jagadeesh, George Rosario Srikanthan, Thambipillai School of Computer Science and Engineering Engineering::Computer science and engineering Map Matching Speed-up Technique 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. Accepted version 2020-12-30T06:58:44Z 2020-12-30T06:58:44Z 2019 Journal Article 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 2374-0353 https://hdl.handle.net/10356/145630 10.1145/3329676 3 5 en ACM Transactions on Spatial Algorithms and Systems © 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). application/pdf |
| spellingShingle | Engineering::Computer science and engineering Map Matching Speed-up Technique Jagadeesh, George Rosario Srikanthan, Thambipillai Fast computation of clustered many-to-many shortest paths and its application to map matching |
| title | Fast computation of clustered many-to-many shortest paths and its application to map matching |
| title_full | Fast computation of clustered many-to-many shortest paths and its application to map matching |
| title_fullStr | Fast computation of clustered many-to-many shortest paths and its application to map matching |
| title_full_unstemmed | Fast computation of clustered many-to-many shortest paths and its application to map matching |
| title_short | Fast computation of clustered many-to-many shortest paths and its application to map matching |
| title_sort | fast computation of clustered many to many shortest paths and its application to map matching |
| topic | Engineering::Computer science and engineering Map Matching Speed-up Technique |
| url | https://hdl.handle.net/10356/145630 |
| work_keys_str_mv | AT jagadeeshgeorgerosario fastcomputationofclusteredmanytomanyshortestpathsanditsapplicationtomapmatching AT srikanthanthambipillai fastcomputationofclusteredmanytomanyshortestpathsanditsapplicationtomapmatching |