Tight Space Bounds for Pivot-Based Distance Oracles in Sparse Graphs
In the authors' words
An approximate distance oracle (ADO) is a compact data structure that answers distance queries within a multiplicative stretch . The classical oracle of Thorup and Zwick~[STOC'01, JACM'05] has stretch and uses space, for every integer , and this trade-off is optimal for dense graphs under the Erd\H{o}s girth conjecture. However, for sparse graphs (), their lower bound yields nothing beyond space. A pivot-based -hop ADO gives every vertex pivots and returns as an estimate the length of a walk of the form , where is a pivot of , is a pivot of , and is a stored distance. We observe that all the state-of-the-art ADOs with query time are in fact pivot-based -hop ADOs. Our main result is that, under the Erd\H{o}s girth conjecture for graphs with constant degree, there are sparse graphs on which every pivot-based -hop ADO with stretch requires space, for every real . This matches the best known upper bounds with 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 space. In addition, we obtain a tight lower bound for two-hop hopsets. Under the Erd\H{o}s girth conjecture, for every integer , -hopsets on sparse graphs require size , 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 multiplied by .
Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.