Practical Data-Dependent Metric Compression with Provable Guarantees

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.