Fast algorithms speed up geometric spanner construction and distance approximation
Fast Geometric Spanners via Approximate Nearest Neighbor Search
Data Structures and AlgorithmsComputational Geometry
Summary
Building efficient networks that approximate distances quickly often takes a lot of time, especially in complex spaces. The authors show a way to make these constructions faster by using methods that quickly find approximate nearest neighbors. They prove their approach is both time-efficient and nearly the best possible for this problem. Their results also help estimate special distances used in fields like machine learning faster than before in certain spaces.
What this means in practice
- •For data scientists: Quickly approximate Wasserstein distances over high-dimensional datasets in less time using improved network constructions.
- •For computational geometry developers: Build geometric spanners more efficiently for large metric datasets by leveraging fast approximate nearest neighbor queries.
Authors
Alexandr Andoni, Manuel Paez, Krish Singal, Tian Zhang
Abstract
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 $Δ$ admitting a $c$-approximate batch nearest neighbor search algorithm with runtime $τ_{\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 Δ)$ edges and runs in time $\tilde{O}(τ_{\mathsf{M}} \cdot k n^{1/k} \log Δ)$. (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 $Ω(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.