Poster
Practical Data-Dependent Metric Compression with Provable Guarantees
Piotr Indyk · Ilya Razenshteyn · Tal Wagner

Tue Dec 5th 06:30 -- 10:30 PM @ Pacific Ballroom #24 #None
in Posters Tue »

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/epsilon) +log n) bits per point from which one can approximate the distances up to a factor of 1 + epsilon. Our algorithm almost matches the recent bound of Indyk et al, 2017} while being much simpler. We compare our algorithm to Product Quantization (PQ) (Jegou et al, 2011) a state of the art heuristic metric compression method. We evaluate both algorithms on several data sets: SIFT, MNIST, New York City taxi time series and a synthetic one-dimensional data set embedded in a high-dimensional space. Our algorithm produces representations that are comparable to or better than those produced by PQ, while having provable guarantees on its performance.

Keywords: Nonlinear Dimensionality Reduction and Manifold Learning · Similarity and Distance Learning

Author Information

Piotr Indyk (MIT)
Ilya Razenshteyn (Columbia University)
Tal Wagner (MIT)

More from the Same Authors