Practical Data-Dependent Metric Compression with Provable Guarantees

Piotr Indyk, Ilya Razenshteyn, Tal Wagner

We introduce a new distance-preserving compact representation of multi-dimensional point-sets. Given $n$ points in a $d$-dimensional space where each coordinate is represented usin…