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

Abstract

Recently it was shown that the problem of Maximum Inner Product Search (MIPS) is efficient and it admits provably sub-linear hashing algorithms. Asymmetric transformations before hashing were the key in solving MIPS which was otherwise hard. In the prior work, 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 hashing. In this work, we provide a different transformation which converts the problem of approximate MIPS into the problem of approximate cosine similarity search which can be efficiently solved using signed random projections. Theoretical analysis show that the new scheme is significantly better than the original scheme for MIPS. Experimental evaluations strongly support the theoretical findings.

arXiv commentarXiv admin note: text overlap with arXiv:1405.5869

References in corpus (4)

• Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)
• The Power of Asymmetry in Binary Hashing
• Coding for Random Projections
• Coding for Random Projections and Approximate Near Neighbor Search

Cited by in corpus (8)

• Personalized PageRank Estimation and Search: A Bidirectional Approach
• On Symmetric and Asymmetric LSHs for Inner Product Search
• Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering
• Foundations of Vector Retrieval
• When Hashes Met Wedges: A Distributed Algorithm for Finding High Similarity Vectors
• SAH: Shifting-aware Asymmetric Hashing for Reverse $k$-Maximum Inner Product Search
• Asymmetric Minwise Hashing
• Input-independent Attention Weights Are Expressive Enough: A Study of Attention in Self-supervised Audio Transformers