Effective indexing for approximate constrained shortest path queries on large road networks
In a constrained shortest path (CSP) query, each edge in the road network is associated with both a length and a cost. Given an origin s, a destination t, and a cost constraint θ, the goal is to find the shortest path from s to t whose total cost does not exceed θ. Because exact CSP is NP-hard, prev...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Conference or Workshop Item |
Language: | English |
Published: |
2017
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/81353 http://hdl.handle.net/10220/43454 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-81353 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-813532020-03-07T11:48:45Z Effective indexing for approximate constrained shortest path queries on large road networks Wang, Sibo Xiao, Xiaokui Yang, Yin Lin, Wenqing School of Computer Science and Engineering Proceedings of the VLDB Endowment Constrained shortest path Large road networks In a constrained shortest path (CSP) query, each edge in the road network is associated with both a length and a cost. Given an origin s, a destination t, and a cost constraint θ, the goal is to find the shortest path from s to t whose total cost does not exceed θ. Because exact CSP is NP-hard, previous work mostly focuses on approximate solutions. Even so, existing methods are still prohibitively expensive for large road networks. Two main reasons are (i) that they fail to utilize the special properties of road networks and (ii) that most of them process queries without indices; the few existing indices consume large amounts of memory and yet have limited effectiveness in reducing query costs. Motivated by this, we propose COLA, the first practical solution for approximate CSP processing on large road networks. COLA exploits the facts that a road network can be effectively partitioned, and that there exists a relatively small set of landmark vertices that commonly appear in CSP results. Accordingly, COLA indexes the vertices lying on partition boundaries, and applies an on-the-fly algorthm called α-Dijk for path computation within a partition, which effectively prunes paths based on landmarks. Extensive experiments demonstrate that on continent-sized road networks, COLA answers an approximate CSP query in sub-second time, whereas existing methods take hours. Interestingly, even without an index, the α-Dijk algorithm in COLA still outperforms previous solutions by more than an order of magnitude. MOE (Min. of Education, S’pore) Published version 2017-07-27T02:19:51Z 2019-12-06T14:29:03Z 2017-07-27T02:19:51Z 2019-12-06T14:29:03Z 2016 Conference Paper Wang, S., Xiao, X., Yang, Y., & Lin, W. (2016). Effective indexing for approximate constrained shortest path queries on large road networks. Proceedings of the VLDB Endowment, 10(2), 61-72. 21508097 https://hdl.handle.net/10356/81353 http://hdl.handle.net/10220/43454 10.14778/3015274.3015277 en Proceedings of the VLDB Endowment This work is licensed under the Creative Commons AttributionNonCommercial-NoDerivatives 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. 12 p. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
country |
Singapore |
collection |
DR-NTU |
language |
English |
topic |
Constrained shortest path Large road networks |
spellingShingle |
Constrained shortest path Large road networks Wang, Sibo Xiao, Xiaokui Yang, Yin Lin, Wenqing Effective indexing for approximate constrained shortest path queries on large road networks |
description |
In a constrained shortest path (CSP) query, each edge in the road network is associated with both a length and a cost. Given an origin s, a destination t, and a cost constraint θ, the goal is to find the shortest path from s to t whose total cost does not exceed θ. Because exact CSP is NP-hard, previous work mostly focuses on approximate solutions. Even so, existing methods are still prohibitively expensive for large road networks. Two main reasons are (i) that they fail to utilize the special properties of road networks and (ii) that most of them process queries without indices; the few existing indices consume large amounts of memory and yet have limited effectiveness in reducing query costs.
Motivated by this, we propose COLA, the first practical solution for approximate CSP processing on large road networks. COLA exploits the facts that a road network can be effectively partitioned, and that there exists a relatively small set of landmark vertices that commonly appear in CSP results. Accordingly, COLA indexes the vertices lying on partition boundaries, and applies an on-the-fly algorthm called α-Dijk for path computation within a partition, which effectively prunes paths based on landmarks. Extensive experiments demonstrate that on continent-sized road networks, COLA answers an approximate CSP query in sub-second time, whereas existing methods take hours. Interestingly, even without an index, the α-Dijk algorithm in COLA still outperforms previous solutions by more than an order of magnitude. |
author2 |
School of Computer Science and Engineering |
author_facet |
School of Computer Science and Engineering Wang, Sibo Xiao, Xiaokui Yang, Yin Lin, Wenqing |
format |
Conference or Workshop Item |
author |
Wang, Sibo Xiao, Xiaokui Yang, Yin Lin, Wenqing |
author_sort |
Wang, Sibo |
title |
Effective indexing for approximate constrained shortest path queries on large road networks |
title_short |
Effective indexing for approximate constrained shortest path queries on large road networks |
title_full |
Effective indexing for approximate constrained shortest path queries on large road networks |
title_fullStr |
Effective indexing for approximate constrained shortest path queries on large road networks |
title_full_unstemmed |
Effective indexing for approximate constrained shortest path queries on large road networks |
title_sort |
effective indexing for approximate constrained shortest path queries on large road networks |
publishDate |
2017 |
url |
https://hdl.handle.net/10356/81353 http://hdl.handle.net/10220/43454 |
_version_ |
1681039374452523008 |