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 (58)

• Efficient Natural Language Response Suggestion for Smart Reply
• Personalized PageRank Estimation and Search: A Bidirectional Approach
• Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection
• Open-Retrieval Conversational Question Answering
• On Symmetric and Asymmetric LSHs for Inner Product Search
• Quantization based Fast Inner Product Search
• Hierarchical Memory Networks
• BlackOut: Speeding up Recurrent Neural Network Language Models With Very Large Vocabularies
• Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)
• Feature-aware Diversified Re-ranking with Disentangled Representations for Relevant Recommendation
• Signed Distance-based Deep Memory Recommender
• Clustering is Efficient for Approximate Maximum Inner Product Search
• A New Unbiased and Efficient Class of LSH-Based Samplers and Estimators for Partition Function Computation in Log-Linear Models
• Efficient Algorithms for Personalized PageRank
• Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering
• Foundations of Vector Retrieval
• 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
• Sub-Linear Privacy-Preserving Near-Neighbor Search
• Deep Style Match for Complementary Recommendation
• Sparse Attentive Backtracking: Long-Range Credit Assignment in Recurrent Networks
• Learning to Screen for Fast Softmax Inference on Large Vocabulary Neural Networks
• Curse of "Low" Dimensionality in Recommender Systems
• Candidate Generation with Binary Codes for Large-Scale Top-N Recommendation
• Unsupervised Machine Commenting with Neural Variational Topic Model
• Privacy-preserving Targeted Advertising
• Fast Amortized Inference and Learning in Log-linear Models with Randomly Perturbed Nearest Neighbor Search
• Efficient Inner Product Approximation in Hybrid Spaces
• When Hashes Met Wedges: A Distributed Algorithm for Finding High Similarity Vectors
• On Evaluating Embedding Models for Knowledge Base Completion
• Contextual Fine-to-Coarse Distillation for Coarse-grained Response Selection in Open-Domain Conversations
• SAH: Shifting-aware Asymmetric Hashing for Reverse $k$-Maximum Inner Product Search
• 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
• GB-KMV: An Augmented KMV Sketch for Approximate Containment Similarity Search
• Phrase-Indexed Question Answering: A New Challenge for Scalable Document Comprehension
• Auto-JacoBin: Auto-encoder Jacobian Binary Hashing
• Sublinear Partition Estimation
• Asymmetric Minwise Hashing
• Optimizing Revenue over Data-driven Assortments
• Counterfactual Learning To Rank for Utility-Maximizing Query Autocompletion
• Similarity preserving compressions of high dimensional sparse data
• Detecting the large entries of a sparse covariance matrix in sub-quadratic time
• Extreme Classification in Log Memory
• Binary Subspace Coding for Query-by-Image Video Retrieval
• ProMIPS: Efficient High-Dimensional c-Approximate Maximum Inner Product Search with a Lightweight Index
• Building an Efficient and Effective Retrieval-based Dialogue System via Mutual Learning
• Distantly-Supervised Evidence Retrieval Enables Question Answering without Evidence Annotation
• Exact gradient updates in time independent of output size for the spherical loss family
• Distance-Sensitive hashing
• Binary Latent Representations for Efficient Ranking: Empirical Assessment
• Self-supervised asymmetric deep hashing with margin-scalable constraint
• Low-Precision Quantization for Efficient Nearest Neighbor Search