# Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Aug 2016.

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

- [Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time](https://mlsanity.com/paper/2310.17157/) (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)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph](https://mlsanity.com/paper/2303.06210/) (2023)
- [Linear Bandit Algorithms with Sublinear Time Complexity](https://mlsanity.com/paper/2103.02729/) (2021)
- [Fundamental Limitations on Subquadratic Alternatives to Transformers](https://mlsanity.com/paper/2410.04271/) (2024)
- [DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2107.02736/) (2021)
- [Sublinear Time Algorithm for Online Weighted Bipartite Matching](https://mlsanity.com/paper/2208.03367/) (2022)
- [Terminal Embeddings in Sublinear Time](https://mlsanity.com/paper/2110.08691/) (2021)
- [Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2206.01382/) (2022)
- [Scout Before You Attend: Sketch-and-Walk Sparse Attention for Efficient LLM Inference](https://mlsanity.com/paper/2602.07397/) (2026)
- [Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?](https://mlsanity.com/paper/2101.10905/) (2021)
- [Statistical-Computational Trade-offs for Density Estimation](https://mlsanity.com/paper/2410.23087/) (2024)
- [Explaining the Success of Nearest Neighbor Methods in Prediction](https://mlsanity.com/paper/2502.15900/) (2025)
- [Hashing Learning with Hyper-Class Representation](https://mlsanity.com/paper/2206.02334/) (2022)
- [Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation](https://mlsanity.com/paper/2510.23039/) (2025)
- [Graph-based Nearest Neighbors with Dynamic Updates via Random Walks](https://mlsanity.com/paper/2512.18060/) (2025)
- [Learning Partition Trees for Nearest Neighbor Search](https://mlsanity.com/paper/2607.09909/) (2026)

## Abstract (arXiv)

[See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the c-Approximate Near Neighbor Search problem. For the d-dimensional Euclidean space and n-point datasets, we develop a data structure with space n1 + ρu + o(1) + O(dn) and query time nρq + o(1) + d no(1) for every ρu, ρq ≥ 0 such that: beginequation c2 √ρq + (c2 - 1) √ρu = √2c2 - 1. endequation This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor c > 1, improving upon [Kapralov, PODS 2015]. The data structure is a culmination of a long line of work on the problem for all space regimes; it builds on Spherical Locality-Sensitive Filtering [Becker, Ducas, Gama, Laarhoven, SODA 2016] and data-dependent hashing [Andoni, Indyk, Nguyen, Razenshteyn, SODA 2014] [Andoni, Razenshteyn, STOC 2015]. Our matching lower bounds are of two types: conditional and unconditional. First, we prove tightness of the whole above trade-off in a restricted model of computation, which captures all known hashing-based approaches. We then show unconditional cell-probe lower bounds for one and two probes that match the above trade-off for ρq = 0, improving upon the best known lower bounds from [Panigrahy, Talwar, Wieder, FOCS 2010]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than the one-probe bound. To show the result for two probes, we establish and exploit a connection to locally-decodable codes.