Timezone: »
We show the existence of a Locality-Sensitive Hashing (LSH) family for the angular distance that yields an approximate Near Neighbor Search algorithm with the asymptotically optimal running time exponent. Unlike earlier algorithms with this property (e.g., Spherical LSH (Andoni-Indyk-Nguyen-Razenshteyn 2014) (Andoni-Razenshteyn 2015)), our algorithm is also practical, improving upon the well-studied hyperplane LSH (Charikar 2002) in practice. We also introduce a multiprobe version of this algorithm and conduct an experimental evaluation on real and synthetic data sets.We complement the above positive results with a fine-grained lower bound for the quality of any LSH family for angular distance. Our lower bound implies that the above LSH family exhibits a trade-off between evaluation time and quality that is close to optimal for a natural class of LSH functions.
Author Information
Alexandr Andoni (Columbia)
Piotr Indyk (MIT)
Thijs Laarhoven (TU/e)
Ilya Razenshteyn (MIT)
Ludwig Schmidt (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 -
2018 Poster: Adversarially Robust Generalization Requires More Data »
Ludwig Schmidt · Shibani Santurkar · Dimitris Tsipras · Kunal Talwar · Aleksander Madry -
2018 Spotlight: Adversarially Robust Generalization Requires More Data »
Ludwig Schmidt · Shibani Santurkar · Dimitris Tsipras · Kunal Talwar · Aleksander Madry -
2017 Workshop: Deep Learning: Bridging Theory and Practice »
Sanjeev Arora · Maithra Raghu · Russ Salakhutdinov · Ludwig Schmidt · Oriol Vinyals -
2017 Poster: Practical Data-Dependent Metric Compression with Provable Guarantees »
Piotr Indyk · Ilya Razenshteyn · Tal Wagner -
2017 Poster: Communication-Efficient Distributed Learning of Discrete Distributions »
Ilias Diakonikolas · Elena Grigorescu · Jerry Li · Abhiram Natarajan · Krzysztof Onak · Ludwig Schmidt -
2017 Oral: Communication-Efficient Distributed Learning of Discrete Distributions »
Ilias Diakonikolas · Elena Grigorescu · Jerry Li · Abhiram Natarajan · Krzysztof Onak · Ludwig Schmidt -
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: Differentially Private Learning of Structured Discrete Distributions »
Ilias Diakonikolas · Moritz Hardt · Ludwig Schmidt -
2014 Workshop: Optimal Transport and Machine Learning »
Marco Cuturi · Gabriel Peyré · Justin Solomon · Alexander Barvinok · Piotr Indyk · Robert McCann · Adam Oberman