# Approximate Nearest Neighbors in Limited Space

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2018.

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

- [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 Time Algorithm for Online Weighted Bipartite Matching](https://mlsanity.com/paper/2208.03367/) (2022)

## Abstract (arXiv)

We consider the (1+ε)-approximate nearest neighbor search problem: given a set X of n points in a d-dimensional space, build a data structure that, given any query point y, finds a point x ∈ X whose distance to y is at most (1+ε) minx ∈ X |x-y| for an accuracy parameter ε ∈ (0,1). Our main result is a data structure that occupies only O(ε-2 n log(n) log(1/ε)) bits of space, assuming all point coordinates are integers in the range -nO(1) ldots nO(1), i.e., the coordinates have O(log n) bits of precision. This improves over the best previously known space bound of O(ε-2 n log(n)2), obtained via the randomized dimensionality reduction method of Johnson and Lindenstrauss (1984). We also consider the more general problem of estimating all distances from a collection of query points to all data points X, and provide almost tight upper and lower bounds for the space complexity of this problem.