Approximate Distance Sensitivity Oracles in Subquadratic Space

An $f$-edge fault-tolerant distance sensitive oracle ($f$-DSO) with stretch $\sigma \geq 1$ is a data structure that preprocesses a given undirected, unweighted graph $G$ with $n$ vertices and $m$ edges, and a positive integer $f$. When queried with a pair of vertices $s, t$ and a set $F$ of at most $f$ edges, it returns a $\sigma$-approximation of the $s$-$t$-distance in $G - F$. We study $f$-DSOs that take subquadratic space. Thorup and Zwick [JACM 2005] showed that this is only possible for $\sigma \geq 3$. We present, for any constant $f \geq 1$ and $\alpha \in (0, \frac{1}{2})$, and any $\epsilon > 0$, a randomized $f$-DSO with stretch $3 + \epsilon$ that w.h.p. takes $\tilde{O}(n^{2-\alpha f+1}) \cdot O\left(\frac{\log n}{\epsilon}\right)^{f+2}$ space and has an $O\left(\frac{n^\alpha}{\epsilon^2}\right)$ query time. The time to build the oracle is $\tilde{O}(m n^{2-\alpha f+1}) \cdot O\left(\frac{\log n}{\epsilon}\right)^{f+1}$. We also give an improved construction for graphs with diameter at most $D$. For any positive integer $k$, we devise an $f$-DSO with stretch $2k - 1$ that w.h.p. takes $O(D f + o(1)) n^{1 + \frac{1}{k}}$ space and has $\tilde{O}(D o(1))$ query time, with a preprocessing time of $O(D f + o(1)) m n^{\frac{1}{k}}$. Chechik, Cohen, Fiat, and Kaplan [SODA 2017] devised an $f$-DSO with stretch $1 + \epsilon$ and preprocessing time $O\left(\frac{n^{5 + o(1)}}{\epsilon f}\right)$, albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to $O\left(\frac{m n^{2 + o(1)}}{\epsilon f}\right)$.