TY - GEN

T1 - Approximate distance queries and compact routing in sparse graphs

AU - Agarwal, Rachit

AU - Godfrey, Philip B

AU - Har-Peled, Sariel

PY - 2011/8/2

Y1 - 2011/8/2

N2 - 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 Ω(n1+1/k) for graphs of n nodes. The hard cases that enforce this lower bound are, however, rather dense graphs with average degree Ω(n1/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(n3/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 Õ(n3/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.

AB - 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 Ω(n1+1/k) for graphs of n nodes. The hard cases that enforce this lower bound are, however, rather dense graphs with average degree Ω(n1/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(n3/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 Õ(n3/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.

UR - http://www.scopus.com/inward/record.url?scp=79960871211&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79960871211&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2011.5934973

DO - 10.1109/INFCOM.2011.5934973

M3 - Conference contribution

AN - SCOPUS:79960871211

SN - 9781424499212

T3 - Proceedings - IEEE INFOCOM

SP - 1754

EP - 1762

BT - 2011 Proceedings IEEE INFOCOM

T2 - IEEE INFOCOM 2011

Y2 - 10 April 2011 through 15 April 2011

ER -