Approximate distance queries and compact routing in sparse graphs

An approximate distance query data structure is a compact representation of a graph, and can be queried to approximate shortest paths between any pair of vertices. Any such data structure that retrieves stretch 2k - 1 paths must require space Ω(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 Ω(n^1/k). We present data structures that, for sparse graphs, substantially break that lower bound barrier at the expense of higher query time. For instance, general graphs require O(n^3/2) space and constant query time for stretch 3 paths. For the realistic scenario of a graph with average degree Θ(log n), special cases of our data structures retrieve stretch 2 paths with Õ(n^3/2) space and stretch 3 paths with Õ(n) space, albeit at the cost of Õ(√n) query time. 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.