Indyk, P. and Motwani, R. (1998). Approximate nearest neighbors: towards removing the curse of dimensionality. In Proc. STOC 1998, pp. 604–613. DOI 10.1145/276698.276876
Key takeaways
Read in full (NOTE-905). Approximate nearest-neighbour search in d dimensions reduces, with small overhead, to a decision problem (is there a point within r, or none within (1+ε)r), and that decision problem is solved by locality-sensitive hashing: if hash functions make near pairs collide with probability at least p1 and far pairs with at most p2, then n^ρ random hash tables with ρ = ln(1/p1)/ln(1/p2) answer queries with O(n^ρ) hash evaluations in O(dn + n^{1+ρ}) space, with constant success probability. For Hamming space by bit sampling, and for ℓ_p with p in [1, 2] by embedding, ρ ≤ 1/(1+ε) in the 1999 text (1/ε, for ε > 1, in STOC). The paper also gives the other end of the trade: Õ(d) query time for n·O(1/ε)^d or (nd)^{O(1)} preprocessing. It is an upper bound only: it proves no lower bound, does not claim its exponents are best, solves only the approximate problem with constant probability, and counts preprocessing as space.
Why this is here
QUESTION-114: locality-sensitive hashing, the first organization for similarity queries with sublinear query time in high dimension, paid for in space. The STOC text claims sublinear queries only for approximation factors above 2; the authors’ later draft improves the exponent.