On Symmetric and Asymmetric LSHs for Inner Product Search

Behnam Neyshabur, Nathan Srebro
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1926-1934, 2015.

Abstract

We consider the problem of designing locality sensitive hashes (LSH) for inner product similarity, and of the power of asymmetric hashes in this context. Shrivastava and Li (2014a) argue that there is no symmetric LSH for the problem and propose an asymmetric LSH based on different mappings for query and database points. However, we show there does exist a simple symmetric LSH that enjoys stronger guarantees and better empirical performance than the asymmetric LSH they suggest. We also show a variant of the settings where asymmetry is in-fact needed, but there a different asymmetric LSH is required.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-neyshabur15, title = {On Symmetric and Asymmetric LSHs for Inner Product Search}, author = {Neyshabur, Behnam and Srebro, Nathan}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {1926--1934}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/neyshabur15.pdf}, url = {https://proceedings.mlr.press/v37/neyshabur15.html}, abstract = {We consider the problem of designing locality sensitive hashes (LSH) for inner product similarity, and of the power of asymmetric hashes in this context. Shrivastava and Li (2014a) argue that there is no symmetric LSH for the problem and propose an asymmetric LSH based on different mappings for query and database points. However, we show there does exist a simple symmetric LSH that enjoys stronger guarantees and better empirical performance than the asymmetric LSH they suggest. We also show a variant of the settings where asymmetry is in-fact needed, but there a different asymmetric LSH is required.} }
Endnote
%0 Conference Paper %T On Symmetric and Asymmetric LSHs for Inner Product Search %A Behnam Neyshabur %A Nathan Srebro %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-neyshabur15 %I PMLR %P 1926--1934 %U https://proceedings.mlr.press/v37/neyshabur15.html %V 37 %X We consider the problem of designing locality sensitive hashes (LSH) for inner product similarity, and of the power of asymmetric hashes in this context. Shrivastava and Li (2014a) argue that there is no symmetric LSH for the problem and propose an asymmetric LSH based on different mappings for query and database points. However, we show there does exist a simple symmetric LSH that enjoys stronger guarantees and better empirical performance than the asymmetric LSH they suggest. We also show a variant of the settings where asymmetry is in-fact needed, but there a different asymmetric LSH is required.
RIS
TY - CPAPER TI - On Symmetric and Asymmetric LSHs for Inner Product Search AU - Behnam Neyshabur AU - Nathan Srebro BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-neyshabur15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 1926 EP - 1934 L1 - http://proceedings.mlr.press/v37/neyshabur15.pdf UR - https://proceedings.mlr.press/v37/neyshabur15.html AB - We consider the problem of designing locality sensitive hashes (LSH) for inner product similarity, and of the power of asymmetric hashes in this context. Shrivastava and Li (2014a) argue that there is no symmetric LSH for the problem and propose an asymmetric LSH based on different mappings for query and database points. However, we show there does exist a simple symmetric LSH that enjoys stronger guarantees and better empirical performance than the asymmetric LSH they suggest. We also show a variant of the settings where asymmetry is in-fact needed, but there a different asymmetric LSH is required. ER -
APA
Neyshabur, B. & Srebro, N.. (2015). On Symmetric and Asymmetric LSHs for Inner Product Search. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:1926-1934 Available from https://proceedings.mlr.press/v37/neyshabur15.html.

Related Material