Timezone: »
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.
Author Information
Piotr Indyk (MIT)
Ilya Razenshteyn (Columbia University)
Tal Wagner (MIT)
More from the Same Authors
-
2019 Poster: Estimating Entropy of Distributions in Constant Space »
Jayadev Acharya · Sourbh Bhadane · Piotr Indyk · Ziteng Sun -
2019 Poster: Learning-Based Low-Rank Approximations »
Piotr Indyk · Ali Vakilian · Yang Yuan -
2019 Poster: Space and Time Efficient Kernel Density Estimation in High Dimensions »
Arturs Backurs · Piotr Indyk · Tal Wagner -
2017 Poster: A graph-theoretic approach to multitasking »
Noga Alon · Daniel Reichman · Igor Shinkar · Tal Wagner · Sebastian Musslick · Jonathan D Cohen · Tom Griffiths · Biswadip dey · Kayhan Ozcimder -
2017 Oral: A graph-theoretic approach to multitasking »
Noga Alon · Daniel Reichman · Igor Shinkar · Tal Wagner · Sebastian Musslick · Jonathan D Cohen · Tom Griffiths · Biswadip dey · Kayhan Ozcimder -
2017 Poster: On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks »
Arturs Backurs · Piotr Indyk · Ludwig Schmidt -
2016 Poster: Fast recovery from a union of subspaces »
Chinmay Hegde · Piotr Indyk · Ludwig Schmidt -
2015 Poster: Practical and Optimal LSH for Angular Distance »
Alexandr Andoni · Piotr Indyk · Thijs Laarhoven · Ilya Razenshteyn · Ludwig Schmidt -
2014 Workshop: Optimal Transport and Machine Learning »
Marco Cuturi · Gabriel Peyré · Justin Solomon · Alexander Barvinok · Piotr Indyk · Robert McCann · Adam Oberman