For any є ∈ (0,1), we give a randomized algorithm which given n points in (d, ℓp) for p ∈ [1,2], constructs a directed graph using O(n2 − Ω(є)) edges in nearly-matching time, such that shortest path lengths approximate ℓp-distances up to a (1 + є)-factor. The graph uses non-metric Steiner nodes (known to be necessary) and improves upon the prior construction of Andoni and Zhang using O(n2−Ω(є2)) edges. We show that our construction is nearly-optimal by showing there exists a set of points in d where any (1+є)-approximate directed Steiner spanner must use Ω(n2 − O(є)) edges.

We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwise distances. The novelty is studying average-distortion: for any fixed (yet, arbitrary) distribution $\mu$ over the metric, the sketch should not over-estimate distances, and it should (approximately) preserve the average distance with respect to draws from $\mu$. The notion generalizes average-distortion embeddings into $\ell_{1}$ [1], [2] as well as data-dependent locality-sensitive hashing [3], [4], which have been recently studied in the context of nearest neighbor search.•For all $p \in(2, \infty)$ and any c larger than a fixed constant, we give an average-distortion sketch for ($[\Delta]^{d}, \ell_{p}$) with approximation c and bit-complexity poly $\left(2^{p / c} \cdot \log (d \Delta)\right)$, which is provably impossible in (worst-case) sketching.•As an application, we improve on the approximation of sublinear-time data structures for nearest neighbor search over $\ell_{p}$ (for large $p\gt2$). The prior best approximation was $O(p)$ [2], [4], and we show it can be any c larger than a fixed constant (irrespective of p) by using $n^{O(p / c)}$ space.We give some evidence that $2^{\Omega(p / c)}$ space may be necessary by giving a lower bound on average-distortion sketches which produce a certain probabilistic certificate of farness (which our sketches crucially rely on).

We give new data-dependent locality sensitive hashing schemes (LSH) for the Earth Mover’s Distance (EMD), and as a result, improve the best approximation for nearest neighbor search under EMD by a quadratic factor. Here, the metric EMDs(ℝd,ℓp) consists of sets of s vectors in d, and for any two sets x,y of s vectors the distance EMD(x,y) is the minimum cost of a perfect matching between x,y, where the cost of matching two vectors is their ℓp distance. Previously, Andoni, Indyk, and Krauthgamer gave a (data-independent) locality-sensitive hashing scheme for EMDs(ℝd,ℓp) when p ∈ [1,2] with approximation O(log2 s). By being data-dependent, we improve the approximation to Õ(logs). Our main technical contribution is to show that for any distribution µ supported on the metric EMDs(ℝd, ℓp), there exists a data-dependent LSH for dense regions of µ which achieves approximation Õ(logs), and that the data-independent LSH actually achieves a Õ(logs)-approximation outside of those dense regions. Finally, we show how to “glue” together these two hashing schemes without any additional loss in the approximation. Beyond nearest neighbor search, our data-dependent LSH also gives optimal (distributional) sketches for the Earth Mover’s Distance. By known sketching lower bounds, this implies that our LSH is optimal (up to poly(loglogs) factors) among those that collide close points with constant probability.