pith. sign in

arxiv: 2507.06721 · v2 · submitted 2025-07-09 · 💻 cs.DS

Faster Algorithms for (2k-1)-Stretch Distance Oracles

Avi Kadria , Liam Roditty This is my paper

Pith reviewed 2026-05-19 06:15 UTC · model grok-4.3

classification 💻 cs.DS
keywords distance oraclesstretch factorsgraph algorithmsshortest pathssubquadratic timesamplingclustering
0
0 comments X

The pith

Three new algorithms construct (2k-1)-stretch distance oracles faster than prior methods while using O(n^{1+1/k}) space.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper introduces three new algorithms for building distance oracles that approximate shortest-path distances within a factor of 2k-1 using O(n^{1+1/k}) space. The first algorithm improves the construction time to Ot(max(n^{1+2/k}, m^{1-1/(k-1)} n^{2/(k-1)})) and beats earlier bounds for k greater than 2 when the graph has enough edges. The other two achieve near-linear time in the number of edges for appropriate densities. A reader would care because these speedups make approximate distance queries practical to precompute on larger graphs where exact methods remain too slow.

Core claim

The paper claims three new algorithms that construct a (2k-1)-stretch distance oracle with O(n^{1+1/k}) space. The first runs in Ot(max(n^{1+2/k}, m^{1-1/(k-1)} n^{2/(k-1)})) time and improves on the Ot(min(m n^{1/k}, n^2)) bound of Thorup-Zwick and Baswana-Kavitha for k>2 and m=Omega(n^{1+1/k+eps}). One other runs in Ot(m + n^{3/2 + 3/(4k-6)}) time and improves prior results for 3<k<6 and for k>=6. The last runs in Ot(sqrt(k) m + k n^{1 + 2 sqrt(2)/sqrt(k)}) time and improves the earlier bound for k>=16.

What carries the argument

Improved sampling and clustering primitives inherited from Thorup-Zwick and Baswana-Kavitha that accelerate oracle construction while preserving the space and stretch guarantees.

If this is right

  • Yields the first truly subquadratic-time construction for every 2<k<6.
  • Gives the first linear-time construction for 7-stretch and 9-stretch oracles on graphs with m=n^{2-eps}.
  • Improves the running time for every k>=6 compared with the previous best near-linear algorithm.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Faster construction times could let distance oracles be rebuilt periodically in dynamic settings where graphs change slowly.
  • The same sampling ideas might reduce construction cost for other stretch factors or for oracles that support additional queries such as path reporting.

Load-bearing premise

The sampling and clustering steps from earlier work can be sped up without adding error that would break the (2k-1) stretch guarantee.

What would settle it

Execute the first algorithm on a concrete n-vertex graph with m=Omega(n^{1+1/k+eps}) edges, measure its running time against the claimed bound, and verify that all reported distances satisfy the stretch factor on a set of query pairs.

Figures

Figures reproduced from arXiv: 2507.06721 by Avi Kadria, Liam Roditty.

Figure 1
Figure 1. Figure 1: Comparison between Theorem 3: f(k) = 1/2+ 3 4k−6 and [Wul12]: f(k) = 1/2+2 k+O(1/k2 ) k 2 3 4 5 6 7 8 9 10 [BK10, Wul12] n 1+f(k) n 2 n 2 n 2 n 2 n 1.833 n 1.821 n 1.8125 n 1.722 n 1.717 Theorem 3 − − n 1.8 n 1.714 n 1.667 n 1.636 n 1.615 n 1.6 n 1.588 [PITH_FULL_IMAGE:figures/full_fig_p027_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison between Theorem 5: f(k) = 1 2+ 3 4k +O( 1 k 2 ), Theorem 6: f(k) = 1 2+ 1 2k +O( 1 k 2 ) and [BGSU08]: f(k) = 1 2 + 1 k + O( 1 k 2 ) k 3 4 5 6 7 8 9 10 [BGSU08] n 1+f(k) n 1.917 n 1.792 n 1.725 n 1.683 n 1.655 n 1.634 n 1.618 n 1.606 Theorem 5 n 1.833 n 1.733 n 1.679 n 1.644 n 1.621 n 1.604 n 1.592 n 1.582 [PITH_FULL_IMAGE:figures/full_fig_p028_2.png] view at source ↗
read the original abstract

Let $G=(V, E)$ be an undirected $n$-vertices $m$-edges graph with non-negative edge weights. In this paper, we present three new algorithms for constructing a $(2k-1)$-stretch distance oracle with $O(n^{1+\frac{1}{k}})$ space. The first algorithm runs in $\Ot(\max(n^{1+2/k}, m^{1-\frac{1}{k-1}}n^{\frac{2}{k-1}}))$ time, and improves upon the $\Ot(\min(mn^{\frac{1}{k}},n^2))$ time of Thorup and Zwick [STOC 2001, JACM 2005] and Baswana and Kavitha [FOCS 2006, SICOMP 2010], for every $k > 2$ and $m=\Omega(n^{1+\frac{1}{k}+\eps})$. This yields the first truly subquadratic time construction for every $2 < k < 6$, and nearly resolves the open problem posed by Wulff-Nilsen [SODA 2012] on the existence of such constructions. The two other algorithms have a running time of the form $\Ot(m+n^{1+f(k)})$, which is near linear in $m$ if $m=\Omega(n^{1+f(k)})$, and therefore optimal in such graphs. One algorithm runs in $\Ot(m+n^{\frac32+\frac{3}{4k-6}})$-time, which improves upon the $\Ot(n^2)$-time algorithm of Baswana and Kavitha [FOCS 2006, SICOMP 2010], for $3 < k < 6$, and upon the $\Ot(m+n^{\frac{3}{2}+\frac{2}{k}+O(k^{-2})})$-time algorithm of Wulff-Nilsen [SODA 2012], for every $k\geq 6$. This is the first linear time algorithm for constructing a $7$-stretch distance oracle and a $9$-stretch distance oracle, for graphs with truly subquadratic density.\footnote{with $m=n^{2-\eps}$ for some $\eps > 0$.} The other algorithm runs in $\Ot(\sqrt{k}m+kn^{1+\frac{2\sqrt{2}}{\sqrt{k}}})$ time, (and hence relevant only for $k\ge 16$), and improves upon the $\Ot(\sqrt{k}m+kn^{1+\frac{2\sqrt{6}}{\sqrt{k}}+O(k^{-1})})$ time algorithm of Wulff-Nilsen [SODA 2012] (which is relevant only for $k\ge 96$). ...

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript presents three new algorithms for constructing (2k-1)-stretch distance oracles with O(n^{1+1/k}) space in undirected weighted graphs. The first runs in Ot(max(n^{1+2/k}, m^{1-1/(k-1)} n^{2/(k-1)})) time and improves on Thorup-Zwick and Baswana-Kavitha for k>2 and m=Omega(n^{1+1/k+eps}); the second runs in Ot(m + n^{3/2 + 3/(4k-6)}) time and improves on Baswana-Kavitha for 3<k<6 and Wulff-Nilsen for k>=6; the third runs in Ot(sqrt(k)m + k n^{1 + 2 sqrt(2)/sqrt(k)}) time and improves on Wulff-Nilsen for k>=16. The constructions build on existing sampling and clustering primitives.

Significance. If the results hold, the work provides the first truly subquadratic-time constructions for every 2<k<6 and the first linear-time constructions for 7- and 9-stretch oracles on graphs with m=n^{2-eps}. It nearly resolves the open question of Wulff-Nilsen (SODA 2012) on subquadratic constructions and gives explicit, parameter-free runtime improvements that are optimal when m is sufficiently large. The paper explicitly credits and reuses the Thorup-Zwick sampling (p=n^{-1/k}) and Baswana-Kavitha k-level clustering primitives.

major comments (2)
  1. [§3] §3 (first algorithm): The manuscript must explicitly verify that the accelerated sampling and pruned clustering steps preserve the per-level hit probability of at least 1/n on every shortest path that was used in the original Thorup-Zwick stretch proof. Any reduction below this threshold would invalidate the (2k-1) guarantee without increasing space; the current description states that the primitives are inherited but does not supply the updated probability calculation.
  2. [§5] §5 (second algorithm): The exponent 3/(4k-6) in the n^{3/2 + 3/(4k-6)} term is load-bearing for the claimed improvement over Wulff-Nilsen. The derivation of this specific exponent from the modified clustering radius bounds should be expanded with an explicit recurrence or charging argument so that readers can confirm it does not violate the O(n^{1+1/k}) space bound.
minor comments (2)
  1. [Introduction] The Ot notation is used throughout but never defined; add a sentence in the introduction or preliminaries clarifying that it hides polylog(n) factors.
  2. [Table 1] Table 1 (comparison of running times) should include the precise range of k for which each new bound is asymptotically better than all three baselines, rather than stating the ranges only in the text.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the significance of our results on subquadratic and near-linear constructions of (2k-1)-stretch distance oracles. We address the two major comments below and will incorporate the requested clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: [§3] §3 (first algorithm): The manuscript must explicitly verify that the accelerated sampling and pruned clustering steps preserve the per-level hit probability of at least 1/n on every shortest path that was used in the original Thorup-Zwick stretch proof. Any reduction below this threshold would invalidate the (2k-1) guarantee without increasing space; the current description states that the primitives are inherited but does not supply the updated probability calculation.

    Authors: We agree that an explicit verification strengthens the presentation. The accelerated sampling continues to select each vertex independently with probability n^{-1/k} at every level, and the pruning step is applied only after sampling so that it does not reduce the probability that a shortest path is hit by a sampled vertex within the distance threshold used in the Thorup-Zwick analysis. Consequently the per-level hit probability remains at least 1/n. In the revision we will add a short subsection in §3 that reproduces the relevant probability calculation and confirms that both the stretch bound and the O(n^{1+1/k}) space bound are unchanged. revision: yes

  2. Referee: [§5] §5 (second algorithm): The exponent 3/(4k-6) in the n^{3/2 + 3/(4k-6)} term is load-bearing for the claimed improvement over Wulff-Nilsen. The derivation of this specific exponent from the modified clustering radius bounds should be expanded with an explicit recurrence or charging argument so that readers can confirm it does not violate the O(n^{1+1/k}) space bound.

    Authors: We thank the referee for this request. The exponent arises from balancing the per-level clustering radius r_i = n^{1/(2k-3)} against the number of levels while charging the expected number of portals and cluster centers to the O(n^{1+1/k}) space budget. In the revised §5 we will present an explicit recurrence for the expected cluster size after each round of the modified Baswana-Kavitha procedure together with a charging argument that bounds the total space by O(n^{1+1/k}) and yields the stated time exponent 3/(4k-6). This will make the derivation self-contained. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit algorithmic constructions with independent analysis

full rationale

The paper describes three explicit algorithmic constructions that modify sampling and clustering steps from the Thorup-Zwick and Baswana-Kavitha primitives while preserving the (2k-1) stretch and O(n^{1+1/k}) space bounds through direct probability arguments on path preservation. Running-time bounds are obtained by analyzing the modified cluster computation and pruned sampling procedures in the full manuscript sections on each algorithm; these reductions rely on standard graph-theoretic counting and do not invoke self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation chain is therefore self-contained against the external benchmarks of the cited prior algorithms and does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The constructions rest on standard undirected-graph assumptions and the correctness of prior sampling primitives; no new free parameters, ad-hoc constants, or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Graph is undirected with non-negative edge weights
    Stated in the first sentence of the abstract; required for the distance-oracle definitions to make sense.

pith-pipeline@v0.9.0 · 6053 in / 1347 out tokens · 33210 ms · 2026-05-19T06:15:34.344079+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · 1 internal anchor

  1. [1]

    Stronger 3-sum lower bounds for approximate distance oracles via additive combinatorics

    [ABF23] Amir Abboud, Karl Bringmann, and Nick Fischer. Stronger 3-sum lower bounds for approximate distance oracles via additive combinatorics. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Com- puting, STOC 2023, Orlando, FL, USA, June 20-23, 2023 , pages 391–404. ACM,

    work page 2023

  2. [2]

    Hardness of approxima- tion in p via short cycle removal: cycle detection, distance oracles, and beyond

    [ABKZ22] Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir. Hardness of approxima- tion in p via short cycle removal: cycle detection, distance oracles, and beyond. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 , pages 1487–1500. ACM,

    work page 2022

  3. [3]

    In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Sym- posium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013 , pages 526–538. SIAM,

    work page 2013

  4. [4]

    The space-stretch-time tradeoff in distance oracles

    [Aga14] Rachit Agarwal. The space-stretch-time tradeoff in distance oracles. In Andreas S. Schulz and Dorothea Wagner, editors, Algorithms - ESA 2014 - 22th Annual Euro- pean Symposium, Wroclaw, Poland, September 8-10,

    work page 2014

  5. [5]

    Faster Approximate Distance Queries and Compact Routing in Sparse Graphs

    [AGH12] Rachit Agarwal, Brighten Godfrey, and Sariel Har-Peled. Faster approximate distance queries and compact routing in sparse graphs. CoRR, abs/1201.2703,

    work page internal anchor Pith review Pith/arXiv arXiv

  6. [6]

    Distance or- acles for unweighted graphs: Breaking the quadratic barrier with constant additive error

    [BGSU08] Surender Baswana, Akshay Gaur, Sandeep Sen, and Jayant Upadhyay. Distance or- acles for unweighted graphs: Breaking the quadratic barrier with constant additive error. In Luca Aceto, Ivan Damg˚ ard, Leslie Ann Goldberg, Magn´ us M. Halld´ orsson, Anna Ing´ olfsd´ ottir, and Igor Walukiewicz, editors,Automata, Languages and Program- ming, 35th Int...

    work page 2008

  7. [7]

    (1 + eps)-approximate f - sensitive distance oracles

    [CCFK17] Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. (1 + eps)-approximate f - sensitive distance oracles. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 , pages 1479–1496. SIAM,

    work page 2017

  8. [8]

    New additive spanners

    [Che13] Shiri Chechik. New additive spanners. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013 , pages 498–512. SIAM,

    work page 2013

  9. [9]

    Approximate distance oracles with constant query time

    23 [Che14] Shiri Chechik. Approximate distance oracles with constant query time. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014 , pages 654–663. ACM,

    work page 2014

  10. [10]

    Approximate distance oracles with improved bounds

    [Che15] Shiri Chechik. Approximate distance oracles with improved bounds. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 1–10. ACM,

    work page 2015

  11. [11]

    Path-reporting distance oracles with logarithmic stretch and linear size

    [CZ24] Shiri Chechik and Tianyi Zhang. Path-reporting distance oracles with logarithmic stretch and linear size. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Pro- gramming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia , volume 297 of LIPIcs, pages 42:1–42:18. Schlos...

    work page 2024

  12. [12]

    Path-reporting distance oracles with logarithmic stretch and size o(n log log n)

    [ES23] Michael Elkin and Idan Shabat. Path-reporting distance oracles with logarithmic stretch and size o(n log log n). In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023 , pages 2278–2311. IEEE,

    work page 2023

  13. [13]

    [GLNS02] Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, and Michiel H. M. Smid. Approximate distance oracles for geometric graphs. In David Eppstein, editor, Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA , pages 828–837. ACM/SIAM,

    work page 2002

  14. [14]

    On the space usage of approximate distance oracles with sub-2 stretch

    [KKR24] Tsvi Kopelowitz, Ariel Korin, and Liam Roditty. On the space usage of approximate distance oracles with sub-2 stretch. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia , volume 297 of LIPIcs, pages 101:1–...

    work page 2024

  15. [15]

    Approximate distance oracles for planar graphs with subpolynomial error dependency

    [Le23] Hung Le. Approximate distance oracles for planar graphs with subpolynomial error dependency. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 24 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 , pages 1877–1904. SIAM,

    work page 2023

  16. [16]

    Ramsey partitions and proximity data structures

    [MN06] Manor Mendel and Assaf Naor. Ramsey partitions and proximity data structures. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings , pages 109–118. IEEE Computer Society,

    work page 2006

  17. [17]

    Bypassing erd˝ os’ girth conjecture: Hybrid stretch and sourcewise span- ners

    [Par14] Merav Parter. Bypassing erd˝ os’ girth conjecture: Hybrid stretch and sourcewise span- ners. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, edi- tors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II , volume 8573 of Lecture No...

    work page 2014

  18. [18]

    Deterministic constructions of approxi- mate distance oracles and spanners

    [RTZ05] Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approxi- mate distance oracles and spanners. In Lu´ ıs Caires, Giuseppe F. Italiano, Lu´ ıs Monteiro, Catuscia Palamidessi, and Moti Yung, editors,Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Pro- ceedin...

    work page 2005

  19. [19]

    Spanners and emulators with sublinear distance errors

    [TZ06] Mikkel Thorup and Uri Zwick. Spanners and emulators with sublinear distance errors. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algo- rithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006 , pages 802–809. ACM Press,

    work page 2006

  20. [20]

    Approximate distance oracles with improved preprocessing time

    [Wul12] Christian Wulff-Nilsen. Approximate distance oracles with improved preprocessing time. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012 , pages 202–208. SIAM,

    work page 2012

  21. [21]

    Approximate distance oracles for planar graphs with improved query time-space tradeoff

    [Wul16] Christian Wulff-Nilsen. Approximate distance oracles for planar graphs with improved query time-space tradeoff. In Robert Krauthgamer, editor, Proceedings of the Twenty- Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arling- ton, V A, USA, January 10-12, 2016 , pages 351–362. SIAM,

    work page 2016