Approximate Nearest Neighbors in Limited Space
share
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+ϵ) _x ∈ Xx-y for an accuracy parameter ϵ∈ (0,1). Our main result is a data structure that occupies only O(ϵ^-2 n (n) (1/ϵ)) bits of space, assuming all point coordinates are integers in the range {-n^O(1)... n^O(1)}, i.e., the coordinates have O( n) bits of precision. This improves over the best previously known space bound of O(ϵ^-2 n (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.
READ FULL TEXT