# Optimal (Euclidean) Metric Compression

arXiv: https://arxiv.org/abs/2110.03152 · HTML: https://mlsanity.com/paper/2110.03152/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2021.

## Built on by (most cited first, 1 of 1)

- [Clustering the Sketch: A Novel Approach to Embedding Table Compression](https://mlsanity.com/paper/2210.05974/) (2022)

## Abstract (arXiv)

We study the problem of representing all distances between n points in mathbb Rd, with arbitrarily small distortion, using as few bits as possible. We give asymptotically tight bounds for this problem, for Euclidean metrics, for ℓ1 (a.k.a.~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 theorem of Johnson and Lindenstrauss (Contemp.~Math.~1984). Since it is known that no better dimension reduction is possible, our results establish that Euclidean metric compression is possible beyond dimension reduction.