We present two algorithms for the approximate nearest neighbor problem in high-dimensional spaces. For data sets of size $n$ living in ${\mathbb R}^d$, the algorithms require space that is only polynomial in $n$ and $d$, while achieving query times that are sub-linear in $n$ and polynomial in $d$. We also show applications to other high-dimensional geometric problems, such as the approximate minimum spanning tree.

The article is based on the material from the authors' STOC'98 and FOCS'01 papers. It unifies, generalizes, and simplifies the results from those papers.