mlsanityData to 7 Oct 2026

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

arXiv 1405.5869 ↗First posted 22 May 2014stat.ML cs.DS cs.IRcited by 109

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 109 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 May 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 32; 2022: 21; 2023: 22; 2024: 14; 2025: 6; 2026: 13.

109 papers.

Sort:

By area:

  1. 2020REALM: Retrieval-Augmented Language Model Pre-Trainingcited by 2,126
  2. 2022Socratic Models: Composing Zero-Shot Multimodal Reasoning with Languagecited by 513
  3. 2024Actions Speak Louder than Words: Trillion-Parameter Sequential Transducers for Generative Recommendationscited by 184
  4. 2021Retrieving and Reading: A Comprehensive Survey on Open-domain Question Answeringcited by 178
  5. 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 128
  6. 2022REVEAL: Retrieval-Augmented Visual-Language Pre-Training with Multi-Source Multimodal Knowledge Memorycited by 122
  7. 2022The Lazy Neuron Phenomenon: On Emergence of Activation Sparsity in Transformerscited by 121
  8. 2023Open-domain Visual Entity Recognition: Towards Recognizing Millions of Wikipedia Entitiescited by 112
  9. 2024MagicPIG: LSH Sampling for Efficient LLM Generationcited by 112
  10. 2021TopiOCQA: Open-domain Conversational Question Answering with Topic Switchingcited by 95
  11. 2021End-to-End Training of Neural Retrievers for Open-Domain Question Answeringcited by 75
  12. 2021Neural Machine Translation with Monolingual Translation Memorycited by 61
38 more
  1. 2021The Web Is Your Oyster - Knowledge-Intensive NLP against a Very Large Web Corpuscited by 60
  2. 2023Learning to Rank in Generative Retrievalcited by 46
  3. 2021Multi-task Retrieval for Knowledge-Intensive Taskscited by 44
  4. 2021SelfExplain: A Self-Explaining Architecture for Neural Text Classifierscited by 44
  5. 2021SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Searchcited by 35
  6. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  7. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 32
  8. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  9. 2023Rethinking the Role of Token Retrieval in Multi-Vector Retrievalcited by 28
  10. 2021Multi-Step Reasoning Over Unstructured Text with Beam Dense Retrievalcited by 25
  11. 2021Topology Distillation for Recommender Systemcited by 24
  12. 2024HashAttention: Semantic Sparsity for Faster Inferencecited by 23
  13. 2021RetGen: A Joint framework for Retrieval and Grounded Text Generation Modelingcited by 22
  14. 2022Improving Biomedical Information Retrieval with Neural Retrieverscited by 20
  15. 2022A Survey for Efficient Open Domain Question Answeringcited by 20
  16. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  17. 2024Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learningcited by 16
  18. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  19. 2021Extreme Zero-Shot Learning for Extreme Text Classificationcited by 15
  20. 2022Approximate Nearest Neighbor Search under Neural Similarity Metric for Large-Scale Recommendationcited by 14
  21. 2023Revisiting Neural Retrieval on Acceleratorscited by 14
  22. 2025Generative Retrieval and Alignment Model: A New Paradigm for E-commerce Retrievalcited by 13
  23. 2025RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inferencecited by 13
  24. 2021Transductive Learning for Unsupervised Text Style Transfercited by 12
  25. 2024Locality-Sensitive Hashing-Based Efficient Point Transformer with Applications in High-Energy Physicscited by 12
  26. 2024SOAR: Improved Indexing for Approximate Nearest Neighbor Searchcited by 12
  27. 2025Flow Matching with Semidiscrete Couplingscited by 12
  28. 2021Probabilistic Metric Learning with Adaptive Margin for Top-K Recommendationcited by 11
  29. 2021Fuzzy Logic Based Logical Query Answering on Knowledge Graphscited by 11
  30. 2023OPORP: One Permutation + One Random Projectioncited by 11
  31. 2021Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and Morecited by 10
  32. 2023Diversify Question Generation with Retrieval-Augmented Style Transfercited by 10
  33. 2024Retrieval is Accurate Generationcited by 10
  34. 2021Contextual Fine-to-Coarse Distillation for Coarse-grained Response Selection in Open-Domain Conversationscited by 9
  35. 2022TegTok: Augmenting Text Generation via Task-specific and Open-world Knowledgecited by 9
  36. 2021Linear Bandit Algorithms with Sublinear Time Complexitycited by 8
  37. 2021Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filteringcited by 8
  38. 2023Expository Text Generation: Imitate, Retrieve, Paraphrasecited by 8

50 most cited of 109 All 109 (JSON)