Approximate Distance Sensitivity Oracles in Subquadratic Space

An 𝑓 -edge fault-tolerant distance sensitive oracle ( 𝑓 -DSO) with stretch 𝜎 ⩾ 1 is a data structure that preprocesses a given undirected, unweighted graph 𝐺 with 𝑛 vertices and 𝑚 edges, and a positive integer 𝑓 . When queried with a pair of vertices 𝑠, 𝑡 and a set 𝐹 of at most 𝑓 edges, it returns a 𝜎-approximation of the 𝑠-𝑡-distance in 𝐺 -𝐹.

We study 𝑓 -DSOs that take subquadratic space. Thorup and Zwick [JACM 2005] showed that this is only possible for 𝜎 ⩾ 3. We present, for any constant 𝑓 ⩾ 1 and 𝛼 ∈ (0, 1 2 ), and any 𝜀 > 0, a randomized 𝑓 -DSO with stretch 3 + 𝜀 that w.h.p. takes 𝑂(𝑛 2-𝛼 𝑓 +1 ) • 𝑂(log 𝑛/𝜀) 𝑓 +2 space and has an 𝑂(𝑛 𝛼 /𝜀 2 ) query time. The time to build the oracle is 𝑂(𝑚𝑛 2-𝛼 𝑓 +1 ) • 𝑂(log 𝑛/𝜀) 𝑓 +1 . We also give an improved construction for graphs with diameter at most 𝐷. For any positive integer 𝑘, we devise an 𝑓 -DSO with stretch 2𝑘 -1 that w.h.p. takes 𝑂(𝐷 𝑓 +𝑜(1) 𝑛 1+1/𝑘 ) space and has 𝑂(𝐷 𝑜(1) ) query time, with a preprocessing time of 𝑂(𝐷 𝑓 +𝑜(1) 𝑚𝑛 1/𝑘 ).