# Practical and Optimal LSH for Angular Distance

arXiv: https://arxiv.org/abs/1509.02897 · HTML: https://mlsanity.com/paper/1509.02897/

## Key facts

- Cited by 106 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2015.

## Built on by (most cited first, 30 of 106)

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [MagicPIG: LSH Sampling for Efficient LLM Generation](https://mlsanity.com/paper/2410.16179/) (2024)
- [End-to-End Training of Neural Retrievers for Open-Domain Question Answering](https://mlsanity.com/paper/2101.00408/) (2021)
- [Think-in-Memory: Recalling and Post-thinking Enable LLMs with Long-Term Memory](https://mlsanity.com/paper/2311.08719/) (2023)
- [Video Transformers: A Survey](https://mlsanity.com/paper/2201.05991/) (2022)
- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [End-to-End User Behavior Retrieval in Click-Through RatePrediction Model](https://mlsanity.com/paper/2108.04468/) (2021)
- [Does Preprocessing Help Training Over-parameterized Neural Networks?](https://mlsanity.com/paper/2110.04622/) (2021)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Faster Causal Attention Over Large Sequences Through Sparse Flash Attention](https://mlsanity.com/paper/2306.01160/) (2023)
- [Sampling Is All You Need on Modeling Long-Term User Behaviors for CTR Prediction](https://mlsanity.com/paper/2205.10249/) (2022)
- [ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms](https://mlsanity.com/paper/2305.04359/) (2023)
- [EcoFormer: Energy-Saving Attention with Linear Complexity](https://mlsanity.com/paper/2209.09004/) (2022)
- [Shifted Chunk Transformer for Spatio-Temporal Representational Learning](https://mlsanity.com/paper/2108.11575/) (2021)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [TPU-KNN: K Nearest Neighbor Search at Peak FLOP/s](https://mlsanity.com/paper/2206.14286/) (2022)
- [You Only Sample (Almost) Once: Linear Cost Self-Attention Via Bernoulli Sampling](https://mlsanity.com/paper/2111.09714/) (2021)
- [LSG Attention: Extrapolation of pretrained Transformers to long sequences](https://mlsanity.com/paper/2210.15497/) (2022)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries](https://mlsanity.com/paper/2211.12850/) (2022)
- [Scalable Cross-Entropy Loss for Sequential Recommendations with Large Item Catalogs](https://mlsanity.com/paper/2409.18721/) (2024)
- [EraRAG: Efficient and Incremental Retrieval Augmented Generation for Growing Corpora](https://mlsanity.com/paper/2506.20963/) (2025)
- [Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity](https://mlsanity.com/paper/2406.15575/) (2024)
- [Locality-Sensitive Hashing-Based Efficient Point Transformer with Applications in High-Energy Physics](https://mlsanity.com/paper/2402.12535/) (2024)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)
- [Survival Kernets: Scalable and Interpretable Deep Kernel Survival Analysis with an Accuracy Guarantee](https://mlsanity.com/paper/2206.10477/) (2022)
- [RECE: Reduced Cross-Entropy Loss for Large-Catalogue Sequential Recommenders](https://mlsanity.com/paper/2408.02354/) (2024)
- [DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2107.02736/) (2021)
- [Memoria: Resolving Fateful Forgetting Problem through Human-Inspired Memory Architecture](https://mlsanity.com/paper/2310.03052/) (2023)

## 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.