Approximate distance queries and compact routing in sparse graphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication2011 Proceedings IEEE INFOCOM
Number of pages9
StatePublished - 2011
EventIEEE INFOCOM 2011 - Shanghai, China
Duration: Apr 10 2011Apr 15 2011

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X



ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Approximate distance queries and compact routing in sparse graphs'. Together they form a unique fingerprint.

Cite this