Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)

Anshumali Shrivastava Cornell University, Ping Li Rutgers University
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:259-268, 2015.

Abstract

Recently it was shown that the problem of Maximum Inner Product Search (MIPS) is efficient and it admits provably sub-linear hashing algorithms. In \cite{Proc:Shrivastava_NIPS14}, the authors use asymmetric transformations which convert the problem of approximate MIPS into the problem of approximate near neighbor search which can be efficiently solved using L2-LSH. In this work, we revisit the problem of MIPS and argue that the quantizations used in L2-LSH is suboptimal for MIPS compared to signed random projections (SRP) which is another popular hashing scheme for cosine similarity (or correlations). Based on this observation, we provide different asymmetric transformations which convert the problem of approximate MIPS into the problem amenable to SRP instead of L2-LSH. An additional advantage of our scheme is that we also obtain LSH type space partitioning which is not possible with the existing scheme. Our theoretical analysis show that the new scheme is significantly better than the original scheme for MIPS. Experimental evaluations strongly support the theoretical findings. We also provide the first empirical comparison that shows the superiority of hashing over tree based methods \cite{Proc:Ram_KDD12} for MIPS.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-university15e, title = {Improved Asymmetric Locality Sensitive Hashing ({ALSH}) for Maximum Inner Product Search ({MIPS})}, author = {University, Anshumali Shrivastava Cornell and University, Ping Li Rutgers}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {259--268}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/university15e/university15e.pdf}, url = {https://proceedings.mlr.press/r13/university15e.html}, abstract = {Recently it was shown that the problem of Maximum Inner Product Search (MIPS) is efficient and it admits provably sub-linear hashing algorithms. In \cite{Proc:Shrivastava_NIPS14}, the authors use asymmetric transformations which convert the problem of approximate MIPS into the problem of approximate near neighbor search which can be efficiently solved using L2-LSH. In this work, we revisit the problem of MIPS and argue that the quantizations used in L2-LSH is suboptimal for MIPS compared to signed random projections (SRP) which is another popular hashing scheme for cosine similarity (or correlations). Based on this observation, we provide different asymmetric transformations which convert the problem of approximate MIPS into the problem amenable to SRP instead of L2-LSH. An additional advantage of our scheme is that we also obtain LSH type space partitioning which is not possible with the existing scheme. Our theoretical analysis show that the new scheme is significantly better than the original scheme for MIPS. Experimental evaluations strongly support the theoretical findings. We also provide the first empirical comparison that shows the superiority of hashing over tree based methods \cite{Proc:Ram_KDD12} for MIPS.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS) %A Anshumali Shrivastava Cornell University %A Ping Li Rutgers University %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-university15e %I PMLR %P 259--268 %U https://proceedings.mlr.press/r13/university15e.html %V R13 %X Recently it was shown that the problem of Maximum Inner Product Search (MIPS) is efficient and it admits provably sub-linear hashing algorithms. In \cite{Proc:Shrivastava_NIPS14}, the authors use asymmetric transformations which convert the problem of approximate MIPS into the problem of approximate near neighbor search which can be efficiently solved using L2-LSH. In this work, we revisit the problem of MIPS and argue that the quantizations used in L2-LSH is suboptimal for MIPS compared to signed random projections (SRP) which is another popular hashing scheme for cosine similarity (or correlations). Based on this observation, we provide different asymmetric transformations which convert the problem of approximate MIPS into the problem amenable to SRP instead of L2-LSH. An additional advantage of our scheme is that we also obtain LSH type space partitioning which is not possible with the existing scheme. Our theoretical analysis show that the new scheme is significantly better than the original scheme for MIPS. Experimental evaluations strongly support the theoretical findings. We also provide the first empirical comparison that shows the superiority of hashing over tree based methods \cite{Proc:Ram_KDD12} for MIPS. %Z Reissued by PMLR on 04 October 2026.
APA
University, A.S.C. & University, P.L.R.. (2015). Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS). Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:259-268 Available from https://proceedings.mlr.press/r13/university15e.html. Reissued by PMLR on 04 October 2026.

Related Material