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

2014/05/22 by Anshumali Shrivastava, Ping Li, Shrivastava, Anshumali +1 · 13 citations
Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Retrieval (cs.IR) #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.1405.5869

openalex publication_date 2014/05/22 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

We present the first provably sublinear time algorithm for approximate 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.

Citations

• Matrix Factorization Techniques for Recommender Systems

Cited by

• Queries Are Not Alone: Clustering Text Embeddings for Video Search
• Accelerating LLM Inference with Precomputed Query Storage
• Flow Matching with Semidiscrete Couplings
• OneShot: Index-in-Ranking with Neural Scoring for Large-Scale Retrieval
• Distantly-Supervised Evidence Retrieval Enables Question Answering without Evidence Annotation
• GB-KMV: An Augmented KMV Sketch for Approximate Containment Similarity Search
• Deep Style Match for Complementary Recommendation
• ProMIPS: Efficient High-Dimensional c-Approximate Maximum Inner Product Search with a Lightweight Index
• Similarity preserving compressions of high dimensional sparse data
• Sampling-Decomposable Generative Adversarial Recommender
• Bidding-Aware Retrieval for Multi-Stage Consistency in Online Advertising
• Quantization based Fast Inner Product Search
• Random-Access Ranked Retrieval and Similarity Search

Related

• Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)
• Norm-Ranging LSH for Maximum Inner Product Search
• On Symmetric and Asymmetric LSHs for Inner Product Search
• Norm-Range Partition: A Universal Catalyst for LSH based Maximum Inner Product Search (MIPS)
• Sublinear Maximum Inner Product Search using Concomitants of Extreme Order Statistics