Average Distortion Sketching

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