On Symmetric and Asymmetric LSHs for Inner Product Search

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 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.

arXiv comment11 pages, 3 figures, In Proceedings of The 32nd International Conference on Machine Learning (ICML)

References in corpus (3)

• Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)
• The Power of Asymmetry in Binary Hashing
• Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)

Cited by in corpus (11)

• Quantization based Fast Inner Product Search
• Implementation Notes for the Soft Cosine Measure
• On the Complexity of Inner Product Similarity Join
• Clustering is Efficient for Approximate Maximum Inner Product Search
• Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering
• Foundations of Vector Retrieval
• Fast Amortized Inference and Learning in Log-linear Models with Randomly Perturbed Nearest Neighbor Search
• 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
• Pyramid: A General Framework for Distributed Similarity Search