mlsanityData to 7 Oct 2026

On Symmetric and Asymmetric LSHs for Inner Product Search

arXiv 1410.5518 ↗First posted 21 Oct 2014stat.ML cs.DS cs.IRcited by 23

Not on the map. Why?

Abstract (arXiv)

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 8; 2023: 2; 2024: 3; 2025: 1; 2026: 3.

23 papers.

Sort:

By area:

  1. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  2. 2021Efficient Passage Retrieval with Hashing for Open-domain Question Answeringcited by 53
  3. 2024HashAttention: Semantic Sparsity for Faster Inferencecited by 23
  4. 2022A Survey for Efficient Open Domain Question Answeringcited by 20
  5. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  6. 2022TPU-KNN: K Nearest Neighbor Search at Peak FLOP/scited by 18
  7. 2021You Only Sample (Almost) Once: Linear Cost Self-Attention Via Bernoulli Samplingcited by 17
  8. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  9. 2021Linear Bandit Algorithms with Sublinear Time Complexitycited by 8
  10. 2021Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filteringcited by 8
  11. 2024IceFormer: Accelerated Inference with Long-Sequence Transformers on CPUscited by 8
  12. 2022Sublinear Time Algorithm for Online Weighted Bipartite Matchingcited by 7
11 more
  1. 2022Flashlight: Scalable Link Prediction with Effective Decoderscited by 7
  2. 2023Efficient Link Prediction via GNN Layers Induced by Negative Samplingcited by 6
  3. 2022Implicit Two-Tower Policiescited by 3
  4. 2022Faster Maximum Inner Product Search in High Dimensionscited by 3
  5. 2024Curator: Efficient Indexing for Multi-Tenant Vector Databasescited by 3
  6. 2025SINDI: An Efficient Index for Sparse Vector Approximate Maximum Inner Product Searchcited by 2
  7. 2022Fast Vocabulary Projection Method via Clustering for Multilingual Machine Translation on GPUcited by 1
  8. 2022SAH: Shifting-aware Asymmetric Hashing for Reverse k-Maximum Inner Product Searchcited by 1
  9. 2026Amortized Maximum Inner Product Search with Learned Support Functionscited by 1
  10. 2026Fast-MWEM: Private Data Release in Sublinear Timecited by 0
  11. 2026NBQ: Next-Best-Question for Dynamic Profilingcited by 0