# Optimal Data-Dependent Hashing for Approximate Near Neighbors

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jan 2015.

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

- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (2023)
- [MagicPIG: LSH Sampling for Efficient LLM Generation](https://mlsanity.com/paper/2410.16179/) (2024)
- [A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge](https://mlsanity.com/paper/2310.11703/) (2023)
- [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)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration](https://mlsanity.com/paper/2305.08367/) (2023)
- [A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph](https://mlsanity.com/paper/2303.06210/) (2023)
- [SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddings](https://mlsanity.com/paper/2112.05872/) (2021)
- [Survival Kernets: Scalable and Interpretable Deep Kernel Survival Analysis with an Accuracy Guarantee](https://mlsanity.com/paper/2206.10477/) (2022)
- [Fundamental Limitations on Subquadratic Alternatives to Transformers](https://mlsanity.com/paper/2410.04271/) (2024)
- [Hardness and Algorithms for Robust and Sparse Optimization](https://mlsanity.com/paper/2206.14354/) (2022)
- [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)
- [Automating Nearest Neighbor Search Configuration with Constrained Optimization](https://mlsanity.com/paper/2301.01702/) (2023)
- [Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2206.01382/) (2022)
- [A Near-Linear Time Algorithm for the Chamfer Distance](https://mlsanity.com/paper/2307.03043/) (2023)
- [Data Structures for Density Estimation](https://mlsanity.com/paper/2306.11312/) (2023)
- [Scout Before You Attend: Sketch-and-Walk Sparse Attention for Efficient LLM Inference](https://mlsanity.com/paper/2602.07397/) (2026)
- [SQUASH: Serverless and Distributed Quantization-based Attributed Vector Similarity Search](https://mlsanity.com/paper/2502.01528/) (2025)
- [Metric-Fair Classifier Derandomization](https://mlsanity.com/paper/2206.07826/) (2022)
- [Explaining the Success of Nearest Neighbor Methods in Prediction](https://mlsanity.com/paper/2502.15900/) (2025)
- [Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectors](https://mlsanity.com/paper/2507.21989/) (2025)
- [Stars: Tera-Scale Graph Building for Clustering and Graph Learning](https://mlsanity.com/paper/2212.02635/) (2022)
- [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)
- [DASH-KV: Accelerating Long-Context LLM Inference via Asymmetric KV Cache Hashing](https://mlsanity.com/paper/2604.19351/) (2026)
- [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)

## Abstract (arXiv)

We show an optimal data-dependent hashing scheme for the approximate near neighbor problem. For an n-point data set in a d-dimensional space our data structure achieves query time O(d nρ+o(1)) and space O(n1+ρ+o(1) + dn), where ρ=tfrac12c2-1 for the Euclidean space and approximation c>1. For the Hamming space, we obtain an exponent of ρ=tfrac12c-1. Our result completes the direction set forth in [AINR14] who gave a proof-of-concept that data-dependent hashing can outperform classical Locality Sensitive Hashing (LSH). In contrast to [AINR14], the new bound is not only optimal, but in fact improves over the best (optimal) LSH data structures [IM98,AI06] for all approximation factors c>1. From the technical perspective, we proceed by decomposing an arbitrary dataset into several subsets that are, in a certain sense, pseudo-random.