Approximate Nearest Neighbors In Limited Space

Indyk Piotr, Wagner Tal. Arxiv 2018

[Paper]    
ARXIV Unsupervised

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\in X$ whose distance to $y$ is at most $(1+ϵ)\underset{x\in X}{min}|x-y|$ for an accuracy parameter $ϵ\in (0,1)$. Our main result is a data structure that occupies only $O({ϵ}^{-2}nlog(n)log(1/ϵ))$ bits of space, assuming all point coordinates are integers in the range $\{-n^{O(1)}\dots n^{O(1)}\}$, i.e., the coordinates have $O(logn)$ bits of precision. This improves over the best previously known space bound of $O({ϵ}^{-2}nlog(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.

Similar Work