PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Geometric Spanners via Approximate Nearest Neighbor Search

Alexandr Andoni, Manuel Paez, Krish Singal, Tian Zhang

arXiv:2609.26934v1cs.DScs.CG

TL;DR

Subquadratic-time geometric spanner construction is unclear for general metrics, despite the linear-size input description of the metric points. The paper constructs geometric spanners through black-box access to a BANN oracle and proves a lower bound on the achievable size-distortion trade-off. A truly subquadratic-in-n BANN runtime gives subquadratic spanner construction; algorithms of budget at most Φ incur Ω(ck) distortion, or expected Ω(ck) distortion for randomized algorithms.

  • Problem

    Subquadratic-time geometric spanner construction is unclear for general metrics, despite the linear-size input description of the metric points.

    Source: §1 · p. 2

  • Method

    The paper constructs geometric spanners through black-box access to a BANN oracle and proves a lower bound on the achievable size-distortion trade-off.

    Source: §1.1 · p. 3, §1.1.1 · p. 3

  • Results

    A truly subquadratic-in-n BANN runtime gives subquadratic spanner construction; algorithms of budget at most Φ incur Ω(ck) distortion, or expected Ω(ck) distortion for randomized algorithms.

    Source: §1 · p. 2, §4 · p. 16

  • Takeaways & Limitations

    Truly subquadratic-time spanner construction and subquadratic-time BANN are equivalent up to constant-factor losses.

    Source: §1.1.1 · p. 4

    A Thorup–Zwick variant using the bounded-bunch threshold still incurs exponential-in-k distortion because failed checks provide only a factor-c distance certificate.

    Source: §1.3.1 · p. 7

Abstract

from arXiv · show

We study the problem of constructing metric spanners in general metric spaces in subquadratic time when given blackbox access to a fast algorithm for batch approximate nearest neighbor search. In particular, we show the following results for any metric space $\mathsf{M} = ([n], \mathsf{d})$ with aspect ratio $\Delta$ admitting a $c$-approximate batch nearest neighbor search algorithm with runtime $\tau_{\mathsf{M}}(n)$, (1) There exists an algorithm that, for any $k \in \mathbb{N}$, constructs an $O(c k)$-distortion spanner with $\tilde{O}(kn^{1+1/2k} \log \Delta)$ edges and runs in time $\tilde{O}(\tau_{\mathsf{M}} \cdot k n^{1/k} \log \Delta)$. (2) Any algorithm that learns at most $o(n^{1+1/k}/k)$ pairwise distances by querying a distance oracle and a blackbox batch nearest neighbor search oracle necessarily incurs $\Omega(c k)$ distortion. Our results entail that (truly) sub-quadratic time algorithms for spanner construction is equivalent to subquadratic time BANN (up to constant-factor losses). As a further application, we use our fast spanner constructions to obtain a fast algorithm for approximating the Wasserstein distance $\mathsf{W}_q$, for all $q > 1$, over any metric space admitting an efficient batch approximate nearest neighbor search algorithm. Together with recent new efficient algorithms for approximate nearest neighbor search in $\ell_p$ spaces, for $p > 2$, our results entail the first subquadratic time algorithms for spanner construction (with the stated size-distortion tradeoff) and $\mathsf{W}_q$ distance approximation over these metric spaces.

1 Introduction

The paper asks when geometric spanners can be constructed in subquadratic time and how their construction relates to batch approximate nearest neighbor search (BANN). It uses black-box BANN access to construct spanners and relates the two problems’ subquadratic-time complexity, with a further application to Wasserstein distance approximation.

1 Introduction

  • A classic metric spanner has a size-distortion trade-off, with (2k−1)-distortion and O(n^1+1/k) edges achievable for k in N.The introduction contrasts this established trade-off with the difficulty of constructing geometric spanners quickly.Source: §1 · p. 2
  • Geometric spanners use the complete graph on metric points, but subquadratic construction is not clear even for the classic trade-off.The input description is linear in n although the complete graph has O(n^2) edges.Source: §1 · p. 2
  • The paper asks which metrics admit subquadratic-time geometric spanner construction and whether it reduces black-box to BANN under arbitrary metrics.Existing subquadratic spanner constructions typically leverage ANN or its underlying tools, and spanners can in turn support BANN.Source: §1 · p. 2
  • With black-box BANN access, the paper constructs spanners using sublinear-in-n oracle calls; a truly subquadratic BANN runtime yields subquadratic spanner construction.The paper also establishes equivalence between truly subquadratic spanner construction and subquadratic BANN, up to constant-factor losses.Source: §1 · p. 2
  • The constructions also yield fast Wasserstein-q approximation over metrics with efficient BANN, including ℓ_p spaces for p in (2, ∞].The introduction presents this as an application of lifting graph algorithms through geometric spanners.Source: §1 · p. 2

1.1 Our Results

The section presents BANN-oracle-based spanner construction and a lower bound on its size–distortion trade-off. It also gives Wasserstein-distance algorithms and ℓp-space instantiations.

1.1.1 Spanner Construction and its Tightness

  • For any k, a c-BANN oracle yields an O(ck)-distortion spanner with Õ(kn^(1+1/2k) log Δ) edges in Õ(τM(n) · k n^(1/k) log Δ) time.The spanner is also an O(k)-hop spanner and succeeds with high probability.Source: §1.1.1 · pp. 3–4
  • Subquadratic-time t-spanner construction and t-BANN are equivalent up to constant-factor losses, with the forward reduction giving Oδ(c)-distortion.A c-BANN algorithm running in n^(2−δ) time yields a spanner in O(n^(2−Ω(δ)) log Δ) time.Source: §1.1.1 · p. 4
  • Ω(ck) distortion is required when an algorithm uses n^(1/k) BANN queries, even with n^(1+1/k) additional exact-distance computations.The lower bound is stated for c > 1 and k ≥ 2.Source: §1.1.1 · p. 4

1.1.2 Applications

  • For general metrics with a c-BANN oracle, the paper gives a high-probability O(c k^(2−1/q)) approximation to Wq for q ∈ [1, ∞], with runtime (k²n^(1+1/2k))^(1+o(1)) polylog(UΔ) + Õ(τM(n) · k n^(1/k) log Δ).The algorithm combines the spanner result with a standard reduction to Minimum Cost Flow.Source: §1.1.2 · p. 4
  • Using recent ANN algorithms, the results yield the paper’s best-known time-size-distortion and time-approximation trade-offs for high-dimensional ℓp when p > 2.The cited ANN structure has O(log_p/ε) approximation, n^εd^O(1) query time, and n^(1+εd^O(1)) space and preprocessing time.Source: §1.1.2 · pp. 4–5
  • For ℓp, the paper gives an O(k log_p/ε)-distortion spanner with Õ(k n^(1+1/2k) log Δ) edges and an O(k)-hop bound.Its runtime is n^(1+ε)d^O(1) · k n^(1/k) log Δ; the Wasserstein result gives an O(k^(2−1/q) log_p/ε) approximation for q ∈ [1, ∞].Source: §1.1.2 · p. 5

1.2 Related Work

Prior geometric spanner work spans low- and high-dimensional settings, while subquadratic construction for p > 2 remains an open gap in the cited work. For Wasserstein distances, prior results range from general-metric approximations to faster algorithms in particular geometric settings.

Geometric spanners

  • For p > 2, the cited work identifies a gap between existential spanner guarantees and subquadratic-time constructions.Recent work gives O(t) distortion and eO(n^1+1/t^q) size, with q = p/(p−1), but no subquadratic construction-time bound.Source: §1.2 · p. 5
  • Earlier geometric spanner constructions began in low-dimensional Euclidean space and later extended to high-dimensional settings.The cited examples include high-dimensional directed Steiner spanners and nearly optimal constructions for ℓ_p with p ∈ [1, 2].Source: §1.2 · p. 5

Approximate nearest neighbor search as a primitive

  • ANN methods and locality-sensitive hashing have also supported algorithms for minimum spanning trees, hierarchical clustering, and geometric spanners.Source: §1.2 · p. 5

Wasserstein-q approximation in general metric spaces

  • For arbitrary metrics, cited Wasserstein work includes an O(log n)-approximation for constant q ≥ 2 and a (4 + ε)-approximation for all q ∈ [1, ∞].The paper contrasts these with its use of static offline BANN, a bounded-hop spanner, and minimum-cost flow.Source: §1.2 · p. 5

Wasserstein-q approximation in low-dimensional ℓp spaces

  • In low-dimensional Euclidean settings, prior work gives subquadratic or near-linear algorithms for W1 and faster-than-n^3/2 approximations for planar W2 over uniform distributions.Related work also gives subquadratic algorithms for W∞ over uniform distributions through bottleneck matching.Source: §1.2 · p. 6

Wasserstein-q approximation in high-dimensional ℓp spaces

  • High-dimensional Euclidean spanners have supported subquadratic EMD and Wasserstein algorithms, and later work extends related results to ℓ_p for p ∈ [1, 2].For q = 1 and p ∈ [1, 2], another cited approach reduces approximate EMD to approximate bichromatic closest pair.Source: §1.2 · p. 6

1.3 Technical Overview

The overview develops a geometric Baswana-Sen construction from batch approximate nearest-neighbor search and a lower bound for reductions using few queried distances. Its central ideas are hashing to control attachments and retirement, and a hard metric that forces Ω(ck) distortion.

1.3 Technical Overview

  • The paper’s overview proceeds from the upper bound to the lower bound and then to the Wasserstein-distance application.The upper-bound discussion notes that graph metrics already admit BANN in near-linear time in the number of graph edges.Source: §1.3 · p. 6, §1.3.1 · p. 6

1.3.1 Upper Bound

  • The geometric Baswana-Sen construction replaces graph adjacency with distance scales and uses one BANN call to query all active vertices against sampled clusters.The construction runs independently at scales r = 2^ℓ and unions the resulting edge sets.Source: §1.3.1 · pp. 6, 8
  • Thorup-Zwick gives a natural nearest-neighbor-based starting point, but approximate threshold choices either lose bounded bunch sizes or make distortion exponential in k.The low threshold preserves bounded bunch sizes but chained levels pay the factor c repeatedly; the classic construction has O(k n^1/k) expected bunch size.Source: §1.3.1 · p. 7
  • The one-call approach faces two coupled problems: finding edges to nearby clusters and certifying that none are close, which otherwise yields O(c^2k) distortion.Retiring only when the returned distance exceeds c^2r forces cluster radii to grow by c^2r per iteration.Source: §1.3.1 · p. 8
  • The hashing trick builds candidate lists by isolating clusters in random buckets, then samples only after each list is assembled.A full list supports attachment; an incomplete list is complete within distance r, so retirement edges reach every such cluster and cluster radii grow by cr rather than c^2r per iteration.Source: §1.3.1 · p. 8

1.3.2 Lower Bound

  • The lower bound targets algorithms learning o(n^1+1/k/k) pairwise distances through BANN and exact-distance queries, and seeks Ω(ck) distortion.The hard instance must combine the oracle's Ω(c) approximation with a detour requiring Ω(k) hops.Source: §1.3.2 · pp. 8–9
  • The hard metric uses a high-girth graph with edge weights c except for one uniformly planted edge of weight 1, making detours cost Ω(ck).Limited distance queries and adversarial BANN answers can hide the special edge.Source: §1.3.2 · p. 9
  • To rule out short alternative routes that omit the hidden edge, the proof bounds how many special edges could lie on short paths represented by the spanner.It then plants the edge outside that set after a deterministic generic run and extends the argument to randomized algorithms with Yao’s principle.Source: §1.3.2 · p. 9

1.4 Organization of the Paper

The paper is organized around preliminaries, the spanner upper bound, the lower bound, and a Wasserstein application.

2 Preliminaries

  • Section 2 collects definitions and preliminaries used throughout the paper.Source: §1.4 · p. 9

3–4 Main results

  • Section 3 presents the algorithm and proof of Theorem 1, while Section 4 proves Theorem 2.Source: §1.4 · p. 9

5 Wasserstein application

  • Section 5 applies Theorem 1 to fast Wasserstein-q approximation and proves Corollary 1.2.Source: §1.4 · p. 9

2 Preliminaries

The preliminaries define spanners and nearest-neighbor search, then state a Wasserstein comparison lemma for discrete distributions.

2.1 Spanners

  • A t-spanner bounds shortest-path distances by a factor t, while a k-hop t-spanner also requires a path with exactly k edges.Source: §2.1 · pp. 9–10

2.2 Approximate Nearest Neighbor Search

  • BANN returns an approximate nearest target for each query in a query set, and an ANN data structure yields BANN by preprocessing once and querying each point.The runtime is ρ_M + |Q|·κ_M; the paper assumes the BANN runtime is monotone and bounds query and target set sizes by n.Source: §2.2 · p. 10

2.3 Wasserstein-q distance

  • For distributions in (1/U)Z^n, W_log U is within a factor 2 of W_∞.The proof uses an integral optimal transport solution to obtain a coupling with entries in (1/U)Z^(n×n).Source: §2.3 · pp. 10–11

3 Proof of Theorem 1

The proof establishes that BANN-Spanner constructs a bounded-hop spanner with O(ck) distortion, while accounting for its size and runtime. Its guarantees hold with high probability.

3 Proof of Theorem 1

  • With high probability, every retired vertex has an edge to each nearby cluster, at distance at most cr.The list and sampling events ensure that a retired vertex has recorded the cluster and that its edge is added.Source: §3 · pp. 13–14
  • The proof bounds active clusters in the final round by 10n^(1/(2k)) + 10 log(1000 log Δ) with probability at least 0.999.This bound controls the number of final oracle calls and the final-round edge count.Source: §3 · pp. 14–15
  • The construction runs in ˜O(τ_M(n) · k n^(1/k) log Δ) time.The proof accounts for ˜O(k n^(1/k) log Δ) oracle calls and O(n) work per call.Source: §3 · p. 15
  • The spanner has ˜O(kn^(1+1/(2k)) log Δ) edges.Per scale, the final round contributes O(n^(1+1/(2k)) + n log log Δ) edges, in addition to the earlier iterations.Source: §3 · pp. 14–15
  • With probability at least 0.99, the constructed graph is a (4k−1)-hop spanner with O(ck) distortion.The proof combines scale-specific paths of at most 4k−1 edges with edges weighted by their true metric distances.Source: §3 · p. 15

4 Proof of Theorem 2

With a sub-threshold oracle-query budget, the proof constructs a metric on which spanner distortion is Ω(ck), for deterministic and randomized algorithms. It hides a special short edge so the algorithm cannot learn the short route or a suitable reroute.

4 Proof of Theorem 2

  • The oracle model charges |Q| for a c-BANN call and one per exact distance query, and permits output edges only for pairs whose distances were learned.Consequently, the output spanner has at most Φ edges under budget Φ.Source: §4 · pp. 15–16
  • For every deterministic algorithm with budget at most Φ, some instance yields distortion Ω(ck); for every randomized algorithm with budget at most Φ, some instance yields expected distortion Ω(ck).The lower-bound theorem assumes c > 1 and k ≥ 2.Source: §4 · p. 16

4.1 The instance and the adversary’s policy

  • For c>1 and integer k≥2, the construction starts from a graph of girth at least k+2 with Ω(n^(1+1/k)) edges, samples one edge uniformly as special, and has aspect ratio Λ=Θ(ck).Source: §4.1 · p. 16
  • The adversary answers BANN queries legally while making the special edge difficult to identify from oracle outputs.For distance queries it answers exactly; for BANN, it selects targets according to graph distance and the planted edge policy.Source: §4.1 · p. 17

4.2 The proof of Theorem 4

  • If the special edge is absent but the spanner routes its endpoints below Λ, some spanner edge must have a short graph-shortest path that crosses the special edge.The proof collects such paths in S(H); a budget-limited transcript covers too few graph edges to contain the uniformly planted edge with high probability.Source: §4.2 · pp. 17–19
  • Yao’s principle extends the hidden-edge lower bound to randomized algorithms, yielding expected distortion Ω(ck) on at least one instance.The proof applies the principle to the uniform distribution over instances indexed by the special edge.Source: §4.2 · pp. 19–20

5 Application to W𝑞Distance Approximation

The application reduces Wasserstein distance approximation to minimum-cost flow on a layered graph built from a bounded-hop spanner. It returns an approximate coupling, with its guarantee and runtime depending on the spanner and flow parameters.

5 Application to W𝑞 Distance Approximation

  • The reduction builds a layered min-cost-flow instance from a k-hop D-spanner, assigning spanner-edge costs based on their qth-power lengths.It adds zero-cost edges between successive copies of each point and sets source and sink demands from μ and ν.Source: §5 · p. 21
  • The algorithm returns a coupling whose cost is an O(ck^(2−1/q)) approximation to W_q(μ,ν), with high probability.Its runtime is O(τ_M(n) · k n^(1/k) log Δ) + (k^2 n^(1+1/(2k)))^(1+o(1)) polylog Δ · polylog U.Source: §5 · p. 22

5.1 Proof of Lemma 5.1

  • A feasible flow decomposes into paths from layer 0 to layer k, which yield a coupling supported on at most |E⃗| pairs.The decomposition and coupling extraction take O(k|E⃗| + n) time.Source: §5.1 · pp. 22–23
  • The flow optimum is bounded above by routing an optimal coupling along paths in the spanner, while any feasible flow induces a coupling that lower-bounds its cost.These two comparisons relate the flow objective to the Wasserstein cost.Source: §5.1 · pp. 23–24

Related papers

Loading 2609.26934v1…