mlsanityData to 7 Oct 2026

Practical and Optimal LSH for Angular Distance

arXiv 1509.02897 ↗First posted 9 Sep 2015cs.DS cs.CG cs.IRcited by 105

Not on the map. Why?

Abstract (arXiv)

We show the existence of a Locality-Sensitive Hashing (LSH) family for the angular distance that yields an approximate Near Neighbor Search algorithm with the asymptotically optimal running time exponent. Unlike earlier algorithms with this property (e.g., Spherical LSH [Andoni, Indyk, Nguyen, Razenshteyn 2014], [Andoni, Razenshteyn 2015]), our algorithm is also practical, improving upon the well-studied hyperplane LSH [Charikar, 2002] in practice. We also introduce a multiprobe version of this algorithm, and conduct experimental evaluation on real and synthetic data sets. We complement the above positive results with a fine-grained lower bound for the quality of any LSH family for angular distance. Our lower bound implies that the above LSH family exhibits a trade-off between evaluation time and quality that is close to optimal for a natural class of LSH functions.

Key facts. Cited by 105 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Sep 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 20; 2022: 18; 2023: 12; 2024: 17; 2025: 21; 2026: 17.

105 papers.

Sort:

By area:

  1. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  2. 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 128
  3. 2024MagicPIG: LSH Sampling for Efficient LLM Generationcited by 112
  4. 2021End-to-End Training of Neural Retrievers for Open-Domain Question Answeringcited by 75
  5. 2023Think-in-Memory: Recalling and Post-thinking Enable LLMs with Long-Term Memorycited by 64
  6. 2022Video Transformers: A Surveycited by 63
  7. 2021EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learningcited by 53
  8. 2021End-to-End User Behavior Retrieval in Click-Through RatePrediction Modelcited by 45
  9. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  10. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  11. 2022Sampling Is All You Need on Modeling Long-Term User Behaviors for CTR Predictioncited by 24
  12. 2023ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithmscited by 24
38 more
  1. 2023Faster Causal Attention Over Large Sequences Through Sparse Flash Attentioncited by 24
  2. 2022EcoFormer: Energy-Saving Attention with Linear Complexitycited by 21
  3. 2021Shifted Chunk Transformer for Spatio-Temporal Representational Learningcited by 20
  4. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  5. 2022TPU-KNN: K Nearest Neighbor Search at Peak FLOP/scited by 18
  6. 2021You Only Sample (Almost) Once: Linear Cost Self-Attention Via Bernoulli Samplingcited by 17
  7. 2022LSG Attention: Extrapolation of pretrained Transformers to long sequencescited by 16
  8. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  9. 2024Scalable Cross-Entropy Loss for Sequential Recommendations with Large Item Catalogscited by 15
  10. 2022OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queriescited by 14
  11. 2024Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexitycited by 14
  12. 2025EraRAG: Efficient and Incremental Retrieval Augmented Generation for Growing Corporacited by 14
  13. 2024Locality-Sensitive Hashing-Based Efficient Point Transformer with Applications in High-Energy Physicscited by 12
  14. 2021Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and Morecited by 10
  15. 2022Survival Kernets: Scalable and Interpretable Deep Kernel Survival Analysis with an Accuracy Guaranteecited by 9
  16. 2024RECE: Reduced Cross-Entropy Loss for Large-Catalogue Sequential Recommenderscited by 9
  17. 2021DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Searchcited by 8
  18. 2023Memoria: Resolving Fateful Forgetting Problem through Human-Inspired Memory Architecturecited by 8
  19. 2024LookupFFN: Making Transformers Compute-lite for CPU inferencecited by 8
  20. 2024IceFormer: Accelerated Inference with Long-Sequence Transformers on CPUscited by 8
  21. 2021Learning to Hash Robustly, Guaranteedcited by 7
  22. 2022QUIC-FL: Quick Unbiased Compression for Federated Learningcited by 7
  23. 2022Sublinear Time Algorithm for Online Weighted Bipartite Matchingcited by 7
  24. 2024Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limitscited by 7
  25. 2022Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Searchcited by 6
  26. 2022A Theoretical View on Sparsely Activated Networkscited by 6
  27. 2026Provable Quantization with Randomized Hadamard Transformcited by 6
  28. 2022iFlipper: Label Flipping for Individual Fairnesscited by 5
  29. 2026Scout Before You Attend: Sketch-and-Walk Sparse Attention for Efficient LLM Inferencecited by 4
  30. 2022Faster Maximum Inner Product Search in High Dimensionscited by 3
  31. 2023TBIN: Modeling Long Textual Behavior Data for CTR Predictioncited by 3
  32. 2024Curator: Efficient Indexing for Multi-Tenant Vector Databasescited by 3
  33. 2024Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Searchcited by 3
  34. 2025Explainable and Robust Millimeter Wave Beam Alignment for AI-Native 6G Networkscited by 3
  35. 2025Cracking Vector Search Indexescited by 3
  36. 2025HONEYBEE: Efficient Role-based Access Control for Vector Databases via Dynamic Partitioning[Technical Report]cited by 3
  37. 2026Revisiting RaBitQ and TurboQuant: A Symmetric Comparison of Methods, Theory, and Experimentscited by 3
  38. 2022A Lower Bound of Hash Codes' Performancecited by 2

50 most cited of 105 All 105 (JSON)