Optimal (Euclidean) Metric Compression

Optimal (Euclidean) Metric Compression Indyk, Piotr; Wagner, Tal We study the problem of representing all distances between 𝑛 points in ℝ𝑑, with arbitrarily small distortion, using as few bits as possible. We give asymptotically tight bounds for this problem, for Euclidean metrics, for ℓ1 (also known as Manhattan)-metrics, and for general metrics. Our bounds for Euclidean metrics mark the first improvement over compression schemes based on discretizing the classical dimensionality reduction theo