Effective indexing for approximate constrained shortest path queries on large road networks
Open Access
- 1 October 2016
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 10 (2) , 61-72
Abstract
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.Keywords
This publication has 23 references indexed in Scilit:
- Solving shortest path problems with a weight constraint and replenishment arcsComputers & Operations Research, 2012
- Multiobjective Optimization: Improved FPTAS for Shortest Paths and Non-Linear Objectives with ApplicationsTheory of Computing Systems, 2007
- Δ-stepping: a parallelizable shortest path algorithmJournal of Algorithms, 2003
- Reachability and Distance Queries via 2-Hop LabelsSIAM Journal on Computing, 2003
- An efficient path computation model for hierarchically structured topographical road mapsIEEE Transactions on Knowledge and Data Engineering, 2002
- A simple efficient approximation scheme for the restricted shortest path problemOperations Research Letters, 2001
- A label correcting approach for solving bicriterion shortest-path problemsComputers & Operations Research, 2000
- Hierarchical encoded path views for path query processing: an optimal model and its performance evaluationIEEE Transactions on Knowledge and Data Engineering, 1998
- A dual algorithm for the constrained shortest path problemNetworks, 1980
- A note on two problems in connexion with graphsNumerische Mathematik, 1959