Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)

Abstract

We present the first provably sublinear time algorithm for approximate \emph{Maximum Inner Product Search} (MIPS). Our proposal is also the first hashing algorithm for searching with (un-normalized) inner product as the underlying similarity measure. Finding hashing schemes for MIPS was considered hard. We formally show that the existing Locality Sensitive Hashing (LSH) framework is insufficient for solving MIPS, and then we extend the existing LSH framework to allow asymmetric hashing schemes. Our proposal is based on an interesting mathematical phenomenon in which inner products, after independent asymmetric transformations, can be converted into the problem of approximate near neighbor search. This key observation makes efficient sublinear hashing scheme for MIPS possible. In the extended asymmetric LSH (ALSH) framework, we provide an explicit construction of provably fast hashing scheme for MIPS. The proposed construction and the extended LSH framework could be of independent theoretical interest. Our proposed algorithm is simple and easy to implement. We evaluate the method, for retrieving inner products, in the collaborative filtering task of item recommendations on Netflix and Movielens datasets.

References in corpus (1)

• Coding for Random Projections and Approximate Near Neighbor Search

Cited by in corpus (30)

• Open-Retrieval Conversational Question Answering
• On Symmetric and Asymmetric LSHs for Inner Product Search
• Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)
• Signed Distance-based Deep Memory Recommender
• A New Unbiased and Efficient Class of LSH-Based Samplers and Estimators for Partition Function Computation in Log-Linear Models
• Revisiting Neural Retrieval on Accelerators
• Efficient Exact Gradient Update for training Deep Networks with Very Large Sparse Targets
• A Greedy Approach for Budgeted Maximum Inner Product Search
• Neural Machine Translation with Monolingual Translation Memory
• Sampling-Decomposable Generative Adversarial Recommender
• Deep Style Match for Complementary Recommendation
• Curse of "Low" Dimensionality in Recommender Systems
• Sparse Attentive Backtracking: Long-Range Credit Assignment in Recurrent Networks
• Efficient Inner Product Approximation in Hybrid Spaces
• Fast Amortized Inference and Learning in Log-linear Models with Randomly Perturbed Nearest Neighbor Search
• When Hashes Met Wedges: A Distributed Algorithm for Finding High Similarity Vectors
• Norm-Explicit Quantization: Improving Vector Quantization for Maximum Inner Product Search
• OFAR: A Multimodal Evidence Retrieval Framework for Illegal Live-streaming Identification
• SADIH: Semantic-Aware DIscrete Hashing
• Reference Product Search
• Similarity preserving compressions of high dimensional sparse data
• Asymmetric Minwise Hashing
• Counterfactual Learning To Rank for Utility-Maximizing Query Autocompletion
• Binary Subspace Coding for Query-by-Image Video Retrieval
• Exact gradient updates in time independent of output size for the spherical loss family
• Distantly-Supervised Evidence Retrieval Enables Question Answering without Evidence Annotation
• Building an Efficient and Effective Retrieval-based Dialogue System via Mutual Learning
• ProMIPS: Efficient High-Dimensional c-Approximate Maximum Inner Product Search with a Lightweight Index
• Low-Precision Quantization for Efficient Nearest Neighbor Search
• Binary Latent Representations for Efficient Ranking: Empirical Assessment