跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2610.29624 · v3

A Tight Space Lower Bound for Pivot-Based Distance Oracles

Avi KadriaLiam Roditty
cs.DS
首次提交 2026-10-21 20:09
版本更新 2026-11-01 22:13
雷达观测 2026-11-04 23:43
arXiv ↗PDF ↗

摘要

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$. 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. The main result of this paper is a nearly tight lower bound for pivot-based $1$-hop ADOs in sparse graphs. 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. We prove that every \emph{pivot-based} $1$-hop ADO with \emph{real} stretch $k$ requires $\widetildeΩ(m^{1+2/(k+1)})$ space, under the Erdős girth conjecture for graphs with constant degree. This matches the best known ADOs with $\tilde{O}(1)$ query time, at every known stretch, up to polylogarithmic factors. 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 and improved lower bounds for general $β$-hop hopsets.

查看 arXiv 原文 ↗阅读 PDF ↗

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存，登录后共享已有结果。

版本差异

仅对比实际观测的元数据，不代表 PDF 正文或实验变化。版本可能不连续；带删除线为移除，下划线为新增。

摘要变化

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. thisThis 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. The main result of this paper is a nearly tight lower bound for pivot-based $1$-hop ADOs in sparse graphs. 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 resultWe isprove 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 \emph{real} stretch $k$ requires $\widetildeΩ(m^{1+2/(k+1)})$ space, under the Erdős girth conjecture for everygraphs \emph{real}with $k\ge1$constant degree. This matches the best known upper boundsADOs with $\tilde{O}(1)$ query time, up to polylogarithmic factors, at every known stretch, whereup theyto arepolylogarithmic knownfactors. 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 ADOimproved lower bounds, with the exponentfor abovegeneral $1β$ multiplied by-hop $4/5$hopsets.

观测到的版本

相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。

v3 · 2026-11-01 22:13 · 最新观测版本

A Tight Space Lower Bound for Pivot-Based Distance Oracles

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$. 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. The main result of this paper is a nearly tight lower bound for pivot-based $1$-hop ADOs in sparse graphs. 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. We prove that every \emph{pivot-based} $1$-hop ADO with \emph{real} stretch $k$ requires $\widetildeΩ(m^{1+2/(k+1)})$ space, under the Erdős girth conjecture for graphs with constant degree. This matches the best known ADOs with $\tilde{O}(1)$ query time, at every known stretch, up to polylogarithmic factors. 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 and improved lower bounds for general $β$-hop hopsets.

查看此版本解读 →查看此版本原文 ↗
v2 · 2026-10-27 23:45

A Tight Space Lower Bound for Pivot-Based Distance Oracles

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$.

查看此版本解读 →查看此版本原文 ↗