DO for general metric spaces

The oracle is built of a decreasing collection of k+1 sets of vertices:

• ${\displaystyle A_{0}=V}$
• For every ${\displaystyle i=1,\ldots ,k-1}$: ${\displaystyle A_{i}}$ contains each element of ${\displaystyle A_{i-1}}$, independently, with probability ${\displaystyle n^{-1/k}}$. Note that the expected size of ${\displaystyle A_{i}}$ is ${\displaystyle n^{1-i/k}}$. The elements of ${\displaystyle A_{i}}$ are called i-centers.
• ${\displaystyle A_{k}=\emptyset }$

For every node v, calculate its distance from each of these sets:

• For every ${\displaystyle i=0,\ldots ,k-1}$: ${\displaystyle d(A_{i},v)=\min {(d(w,v)|w\in A_{i}}}$ and ${\displaystyle p_{i}(v)=\arg \min {(d(w,v)|w\in A_{i}}}$. I.e., ${\displaystyle p_{i}(v)}$ is the i-center nearest to v, and ${\displaystyle d(A_{i},v)}$ is the distance between them. Note that for a fixed v, this distance is weakly increasing with i. Also note that for every v, ${\displaystyle d(A_{0},v)=0}$ and ${\displaystyle p_{0}(v)=v}$.
• ${\displaystyle d(A_{k},v)=\infty }$.

For every node v, calculate:

• For every ${\displaystyle i=0,\ldots ,k-1}$: ${\displaystyle B_{i}(v)=\{w\in A_{i}\setminus A_{i+1}|d(w,v)<d(A_{i+1},v)\}}$. ${\displaystyle B_{i}(v)}$ contains all vertices in ${\displaystyle A_{i}}$ which are strictly closer to v than all vertices in ${\displaystyle A_{i+1}}$. The partial unions of ${\displaystyle B_{i}}$s are balls in increasing diameter, that contain vertices with distances up to the first vertex of the next level.

For every v, compute its bunch:

• ${\displaystyle B(v)=\bigcup _{i=0}^{k-1}B_{i}(v).}$

It is possible to show that the expected size of ${\displaystyle B(v)}$ is at most ${\displaystyle kn^{1/k}}$.

For every bunch ${\displaystyle B(v)}$, construct a hash table that holds, for every ${\displaystyle w\in B(V)}$, the distance ${\displaystyle d(w,v)}$.

The total size of the data structure is ${\displaystyle O(kn+\Sigma |B(v)|)=O(kn+nkn^{1/k})=O(kn^{1+1/k})}$

Having this structure initialized, the following algorithm finds the distance between two nodes, u and v:

• ${\displaystyle w:=u,i:=0}$
• while ${\displaystyle w\notin B(v)}$:
  • ${\displaystyle i:=i+1}$
  • ${\displaystyle (u,v):=(v,u)}$ (swap the two input nodes; this does not change the distance between them since the graph is undirected).
  • ${\displaystyle w:=p_{i}(u)}$
• return ${\displaystyle d(w,u)+d(w,v)}$

It is possible to show that, in each iteration, the distance ${\displaystyle d(w,u)}$ grows by at most ${\displaystyle d(v,u)}$. Since ${\displaystyle A_{k-1}\subseteq B(v)}$, there are at most k-1 iterations, so finally ${\displaystyle d(w,u)\leq (k-1)d(v,u)}$. Now by the triangle inequality, ${\displaystyle d(w,v)\leq d(w,u)+d(u,v)\leq kd(v,u)}$, so the distance returned is at most ${\displaystyle (2k-1)d(u,v)}$.

Improvements

The above result was later improved by Patrascu and Roditty^[2] who suggest a DO of size ${\displaystyle O(n^{4/3}m^{1/3})}$ which returns a factor 2 approximation.