Near-Optimal (Euclidean) Metric Compression

Piotr Indyk, Tal Wagner

The metric sketching problem is defined as follows. Given a metric on $n$ points, and $\epsilon >0$, we wish to produce a small size data structure (sketch) that, given any pair of point i…