Approximate distance queries and compact routing in sparse graphs

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

Abstract

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
Pages1754-1762
Number of pages9
DOIs
StatePublished - Aug 2 2011
EventIEEE INFOCOM 2011 - Shanghai, China
Duration: Apr 10 2011Apr 15 2011

Publication series

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

Other

OtherIEEE INFOCOM 2011
CountryChina
CityShanghai
Period4/10/114/15/11

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

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

Cite this