Computer Science – Data Structures and Algorithms
Scientific paper
2012-01-12
Computer Science
Data Structures and Algorithms
20 pages, an earlier version appeared in INFOCOM 2011, this version presents data structures with improved space/query-time tr
Scientific paper
A distance oracle is a compact representation of the shortest distance matrix of a graph. It can be queried to approximate shortest paths between any pair of vertices. Any distance oracle that returns paths of worst-case stretch (2k-1) must require space $\Omega(n^{1 + 1/k})$ for graphs of n nodes. The hard cases that enforce this lower bound are, however, rather dense graphs with average degree \Omega(n^{1/k}). We present distance oracles that, for sparse graphs, substantially break the lower bound barrier at the expense of higher query time. For any 1 \leq \alpha \leq n, our distance oracles can return stretch 2 paths using O(m + n^2/\alpha) space and stretch 3 paths using O(m + n^2/\alpha^2) space, at the expense of O(\alpha m/n) query time. By setting appropriate values of \alpha, we get the first distance oracles that have size linear in the size of the graph, and return constant stretch paths in non-trivial query time. The query time can be further reduced to O(\alpha), by using an additional O(m \alpha) space for all our distance oracles, or at the cost of a small constant additive stretch. We use our stretch 2 distance oracle to present the first compact routing scheme with worst-case stretch 2. Any compact routing scheme with stretch less than 2 must require linear memory at some nodes even for sparse graphs; our scheme, hence, achieves the optimal stretch with non-trivial memory requirements. Moreover, supported by large-scale simulations on graphs including the AS-level Internet graph, we argue that our stretch-2 scheme would be simple and efficient to implement as a distributed compact routing protocol.
Agarwal Rachit
Godfrey Brighten P.
Har-Peled Sariel
No associations
LandOfFree
Faster Approximate Distance Queries and Compact Routing in Sparse Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Faster Approximate Distance Queries and Compact Routing in Sparse Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Approximate Distance Queries and Compact Routing in Sparse Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-468166