arXiv preprint ·
A Tight Space Lower Bound for Pivot-Based Distance Oracles
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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\ell-1$ and uses $O(\ell n^{1+1/\ell})$ space, for every integer $\ell\ge1$, 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 $Ω(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 $\widetildeΩ(m^{1+2/(k+1)})$ space, for every \emph{real} $k\ge1$. 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 $β$ of hops, showing that they require $\widetildeΩ(m^{1+2/(β(k+1))})$ space. In addition, we obtain a tight lower bound for two-hop hopsets. Under the Erdős girth conjecture, for every integer $\ell\ge3$, $(2\ell-3,2)$-hopsets on sparse graphs require size $Ω(m^{1+1/\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/5$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Near-Optimal Consistency-Robustness Bounds for Non-Clairvoyant Scheduling
Optimal Mixing for Local Edge-Coloring Dynamics on Trees
Optimal Labeling Schemes for $Γ$-Free Matrices
Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references
On the Largest Cardinality Subset Sum
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.