Finding alternative shortest paths in spatial networks

Xie, Kexin, Deng, Ke, Shang, Shuo, Zhou, Xiaofang and Zheng, Kai (2012) Finding alternative shortest paths in spatial networks. ACM Transactions On Database Systems, 37 4: 29.1-29.31. doi:10.1145/2389241.2389248

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Xie, Kexin
Deng, Ke
Shang, Shuo
Zhou, Xiaofang
Zheng, Kai
Title Finding alternative shortest paths in spatial networks
Journal name ACM Transactions On Database Systems   Check publisher's open access policy
ISSN 0362-5915
Publication date 2012-12
Sub-type Article (original research)
DOI 10.1145/2389241.2389248
Open Access Status
Volume 37
Issue 4
Start page 29.1
End page 29.31
Total pages 31
Place of publication New York, United States
Publisher sociation for Computing Machinery
Collection year 2013
Language eng
Formatted abstract
Shortest path query is one of the most fundamental queries in spatial network databases. There exist algorithms that can process shortest path queries in real time. However, many complex applications require more than just the calculation of a single shortest path. For example, one of the common ways to determine the importance (or price) of a vertex or an edge in spatial network is to use Vickrey pricing, which intuitively values the vertex v (or edge e) based on how much harder for travelling from the sources to the destinations without using v (or e). In such cases, the alternative shortest paths without using v (or e) are required. In this article, we propose using a precomputation based approach for both single pair alternative shortest path and all pairs shortest paths processing. To compute the alternative shortest path between a source and a destination efficiently, a naïive way is to precompute and store all alternative shortest paths between every pair of vertices avoiding every possible vertex (or edge), which requires O(n4) space. Currently, the state of the art approach for reducing the storage cost is to choose a subset of the vertices as center points, and only store the single-source alternative shortest paths from those center points. Such approach has the space complexity of O(n2 log n). We propose a storage scheme termed iSPQF, which utilizes shortest path quadtrees by observing the relationships between each avoiding vertex and its corresponding alternative shortest paths. We have reduced the space complexity from the naïive O(n4) (or the state of the art O(n4 log n)) to O(min(γ, L)n1.5) with comparable query performance of O(K), where K is the number of vertices in the returned paths, L is the diameter of the spatial network, and γ is a value that depends on the structure of the spatial network, which is empirically estimated to be 40 for real road networks. Experiments on real road networks have shown that the space cost of the proposed iSPQF is scalable, and both the algorithms based on iSPQF are efficient.
Keyword Design
Spatial networks
Shortest paths
Real-time query processing
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ
Additional Notes Article number 29.

Document type: Journal Article
Sub-type: Article (original research)
Collections: Official 2013 Collection
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 2 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 3 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Sun, 10 Feb 2013, 00:37:38 EST by System User on behalf of Scholarly Communication and Digitisation Service