Tight Space Bounds for Pivot-Based Distance Oracles in Sparse Graphs

An approximate distance oracle (ADO) is a compact data structure that answers distance queries within a multiplicative \emph{stretch} $k$. The classical oracle of Thorup and Zwick~[STOC’01, JACM’05] has stretch $k=2\mathrm{\ell }-1$ and uses $O(\mathrm{\ell }{n}^{1+1\mathrm{/}\mathrm{\ell }})$ space, for every integer $\mathrm{\ell }\ge 1$, and this trade-off is optimal for dense graphs under the Erdős girth conjecture. However, for sparse graphs ($m=O(n)$), their lower bound yields nothing beyond $\mathrm{\Omega }(m)$ space. A pivot-based $1$-hop ADO gives every vertex $\tilde{O}(1)$ pivots and returns as an estimate the length of a walk of the form $u\to p_u\to p_v\to v$, where $p_u$ is a pivot of $u$, $p_v$ is a pivot of $v$, and $p_u\to p_v$ is a stored distance. We observe that all the state-of-the-art ADOs with $\tilde{O}(1)$ query time are in fact pivot-based $1$-hop ADOs. Our main result is that, under the Erdős girth conjecture for graphs with constant degree, there are sparse graphs on which every \emph{pivot-based} $1$-hop ADO with stretch $k$ requires $\tilde{\mathrm{\Omega }}(m^{1+2\mathrm{/}(k+1)})$ space, for every \emph{real} $k\ge 1$. This matches the best known upper bounds with $\tilde{O}(1)$ query time, up to polylogarithmic factors, at every stretch where they are known. We also extend our lower bound to pivot-based ADOs with any constant number $\beta$ of hops, showing that they require $\tilde{\mathrm{\Omega }}(m^{1+2\mathrm{/}(\beta (k+1))})$ space. In addition, we obtain a tight lower bound for two-hop hopsets. Under the Erdős girth conjecture, for every integer $\mathrm{\ell }\ge 3$, $(2\mathrm{\ell }-3,2)$-hopsets on sparse graphs require size $\mathrm{\Omega }(m^{1+1\mathrm{/}\mathrm{\ell }})$, which matches a construction based on the oracles of [Kadria and Roditty, ISAAC’25]. Using the recent explicit high-girth graphs of Double Agent~[doubleAI’26], we also obtain unconditional versions of our ADO lower bounds, with the exponent above $1$ multiplied by $4\mathrm{/}5$.