Abstract
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\) [Rabinovich '03, Kush-Nikolov-Tang '21] as well as data-dependent locality-sensitive hashing [Andoni-Razenshteyn '15, Andoni-Naor-Nikolov-et-al. '18], which have been recently studied in the context of nearest neighbor search. \(\bullet\) 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 \(\text\{poly\}(2^\{p/c\} \cdot log(d\Delta))\), which is