Exact and Approximate Nearest Neighbor Queries in Euclidean Space

data base P of n points in a metric space X so that given a query point q in X,
the point in P closest to q can be determined quickly. I consider only the case
in which X is the d-dimensional Euclidean space (with Euclidean metric).
Unfortunately, to achieve a fast query time an impractically large amount of
space is needed, and consequently there is interest in the approximate version
of the problem in which a parameter epsilon is specified and it is sufficient
to find a point in P no farther than the nearest neighbor by a factor 1+epsilon.
Because of the practical importance of the problem, there has been much work on
heuristics; however, I will concentrate on solutions that provide a performance
guarantee.

The main goal will be to present some recent work on approximate nearest neighbor
(third lecture) that achieves query time polynomial in d and log n while using
space polynomial in d and n (for constant epsilon). As a point of reference, I
will present previous work on the exact version (first lecture) and previous work
on the approximate version (second lecture).

Lecture 1: Exact version: Voronoi diagrams and random sampling [Clarkson;
Schwarzkopf]; partition trees [Matousek].