2024/11/07 by Bao, Yiqiao, Baweja, Anubhav, Menand, Nicolas +3
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2411.05156
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 μ over the metric, the sketch should not over-estimate distances, and it should (approximately) preserve the average distance with respect to draws from μ. The notion generalizes average-distortion embeddings into ℓ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 ∈ (2, ∞) and any c larger than a fixed constant, we give an average-distortion sketch for ([Δ]d, ℓp) with approximation c and bit-complexity poly(2p/c ⋅ log(dΔ)), which is provably impossible in (worst-case) sketching. \bullet As an application, we improve on the approximation of sublinear-time data structures for nearest neighbor search over ℓp (for large p > 2). The prior best approximation was O(p) [Andoni-Naor-Nikolov-et-al. '18, Kush-Nikolov-Tang '21], and we show it can be any c larger than a fixed constant (irrespective of p) by using nO(p/c) space. We give some evidence that 2Ω(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).