A survey on distance oracles
Liam Roditty
Computer Science Department - Bar-Ilan University
Ramat-Gan, Israel.

Abstract: Computing shortest paths is one of the most fundamental computational problems. In many applications we are not really interested in *all* distances, we just want the ability to retrieve them quickly, on demand. For instance, in Internet routing we cannot compute all point-to-point distances, and even if we could, it would be impossible to store them all (i.e., the complete distance matrix) in every node of the network. Moreover, the actual amount of point-to-point communication over the Internet is significantly smaller than the possible number of point-to-point pairs. The ideal solution is thus to allow fast retrieval of a routing path on demand.

Thorup and Zwick [STOC'01 and JACM'05] initiated the theoretical study of data structures capable of representing almost shortest paths efficiently, both in terms of space requirement and query time. Given an n-vertex weighted undirected graph with m edges, they show that for any integer {$k \geq 1$} it is possible to preprocess the graph in {$O(m.n^{1/k})$} time and generate a compact data structure of size {$O(n^{1+1/k})$}. For each pair of vertices, it is then possible to retrieve a multiplicative stretch {$2k-1$} approximate distance in {$O(k)$} time. In particular, for {$k=1$} it gives exact distances using the distance matrix of size {$n^2$}, and for {$k=2$} it gives a data structure of size {$O(n^{1.5})$} and stretch 3 approximate distances in constant time. Thorup and Zwick called such data structures distance oracles.

Recently, Patrascu and Roditty [FOCS'10] presented a distance oracle with a multiplicative stretch of 2 and additive stretch of 1 whose space is {$O(n^{5/3})$}, which is in between the {$O(n^{1.5})$} size distance oracle (for {$k=2$}) and the distance matrix of size {$n^2$} (for {$k=1$}) in Thorup-Zwick distance oracles.

In this talk, I will survey the research on distance oracles from Thorup and Zwick seminal paper until the most recent advances in the field.

Presentation Material

Back to TERANET 2011 Homepage