# Beyond Locality-Sensitive Hashing

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2013.

## Built on by (most cited first, 23 of 23)

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [A Survey on Retrieval-Augmented Text Generation for Large Language Models](https://mlsanity.com/paper/2404.10981/) (2024)
- [A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge](https://mlsanity.com/paper/2310.11703/) (2023)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddings](https://mlsanity.com/paper/2112.05872/) (2021)
- [Learning to Hash Robustly, Guaranteed](https://mlsanity.com/paper/2108.05433/) (2021)
- [Sublinear Time Algorithm for Online Weighted Bipartite Matching](https://mlsanity.com/paper/2208.03367/) (2022)
- [MemoryFormer: Minimize Transformer Computation by Removing Fully-Connected Layers](https://mlsanity.com/paper/2411.12992/) (2024)
- [Scout Before You Attend: Sketch-and-Walk Sparse Attention for Efficient LLM Inference](https://mlsanity.com/paper/2602.07397/) (2026)
- [Monitoring Robustness and Individual Fairness](https://mlsanity.com/paper/2506.00496/) (2025)
- [Metric-Fair Classifier Derandomization](https://mlsanity.com/paper/2206.07826/) (2022)
- [Deep Hashing via Householder Quantization](https://mlsanity.com/paper/2311.04207/) (2023)
- [BOLT: An Automated Deep Learning Framework for Training and Deploying Large-Scale Search and Recommendation Models on Commodity CPU Hardware](https://mlsanity.com/paper/2303.17727/) (2023)
- [Leveraging High-Resolution Features for Improved Deep Hashing-based Image Retrieval](https://mlsanity.com/paper/2403.13747/) (2024)
- [Provable Hierarchical Lifelong Learning with a Sketch-based Modular Architecture](https://mlsanity.com/paper/2112.10919/) (2021)
- [The Power of External Memory in Increasing Predictive Model Capacity](https://mlsanity.com/paper/2302.00003/) (2023)
- [Massively-Parallel Heat Map Sorting and Applications To Explainable Clustering](https://mlsanity.com/paper/2309.07486/) (2023)
- [SPINEX-Clustering: Similarity-based Predictions with Explainable Neighbors Exploration for Clustering Problems](https://mlsanity.com/paper/2407.07222/) (2024)
- [Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search](https://mlsanity.com/paper/2505.15636/) (2025)
- [Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation](https://mlsanity.com/paper/2510.23039/) (2025)
- [SubQuad: Near-Quadratic-Free Structure Inference with Distribution-Balanced Objectives in Adaptive Receptor framework](https://mlsanity.com/paper/2602.17330/) (2026)
- [Hyperdimensional Cross-Modal Alignment of Frozen Language and Image Models for Efficient Image Captioning](https://mlsanity.com/paper/2602.23588/) (2026)
- [Learning Partition Trees for Nearest Neighbor Search](https://mlsanity.com/paper/2607.09909/) (2026)

## Abstract (arXiv)

We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in Rd, our algorithm achieves O(nρ + d log n) query time and O(n1 + ρ + d log n) space, where ρ <= 7/(8c2) + O(1 / c3) + o(1). This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality-sensitive hashing lower bound proved by O'Donnell, Wu and Zhou (ICS 2011). By a standard reduction we obtain a data structure for the Hamming space and ℓ1 norm with ρ <= 7/(8c) + O(1/c3/2) + o(1), which is the first improvement over the result of Indyk and Motwani (STOC 1998).