Distance oracle

In computing, a distance oracle is a data structure for calculating distances between vertices in a graph.

Introduction

Let G(V,E) be an undirected, weighted graph, with n=|V| nodes and m=|E| edges. We would like to answer queries of the form "what is the distance between the nodes s and t?".

One way to do this is just run the Dijkstra algorithm. This takes time $O(m+n\log n)$, and requires no extra space (besides the graph itself).

In order to answer many queries more efficiently, we can spend some time in pre-processing the graph and creating an auxiliary data structure.

A simple data structure that achieves this goal is a matrix which specifies, for each pair of nodes, the distance between them. This structure allows us to answer queries in constant time $O(1)$, but requires $O(n^{2})$ extra space. It can be initialized in time $O(n^{3})$ using an all-pairs shortest paths algorithm, such as the Floyd–Warshall algorithm.

The distance oracle lies between these two extremes. It less than $O(n^{2})$ space in order to answer queries in less than $O(m+n\log n)$ time.

Thorup and Zwick approximate distance oracle

Thorup and Zwick presented a data structure that, for every k, requires space $O(kn^{1+1/k})$, such that any subsequent distance query can be approximately answered in time $O(k)$. The approximate distance returned is of stretch at most $2k-1$, that is, the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and $2k-1$. The initialization time is $O(kmn^{1/k})$.

Some special cases include:

• For $k=1$ we get the simple distance matrix.
• For $k=2$ we get a structure using $O(n^{1.5})$ space which answers each query in constant time and approximation factor at most 3.
• For Failed to parse (unknown function "\floor"): {\displaystyle k=\floor \log n \rfloor} , we get a structure using $O(n\log n)$ space, query time $O(logn)$, and stretch $O(\log n)$.

Higher values of k do not improve the space or preprocessing time.