# Practical Data-Dependent Metric Compression with Provable Guarantees

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

## Key facts

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

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

- [Stars: Tera-Scale Graph Building for Clustering and Graph Learning](https://mlsanity.com/paper/2212.02635/) (2022)

## Abstract (arXiv)

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 using B bits (i.e., dB bits per point), it produces a representation of size O( d log(d B/ε) + log n) bits per point from which one can approximate the distances up to a factor of 1 ± ε. Our algorithm almost matches the recent bound of~citeindyk2017near while being much simpler. We compare our algorithm to Product Quantization (PQ)~citejegou2011product, a state of the art heuristic metric compression method. We evaluate both algorithms on several data sets: SIFT (used in citejegou2011product), MNIST~citelecun1998mnist, New York City taxi time series~citeguha2016robust and a synthetic one-dimensional data set embedded in a high-dimensional space. With appropriately tuned parameters, our algorithm produces representations that are comparable to or better than those produced by PQ, while having provable guarantees on its performance.