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...

Full description

Saved in:
Bibliographic Details
Main Authors: Wang, Sibo, Xiao, Xiaokui, Yang, Yin, Lin, Wenqing
Other Authors: School of Computer Science and Engineering
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