Theory of Computing ------------------- Title : Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality Authors : Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani Volume : 8 Number : 14 Pages : 321-350 URL : https://theoryofcomputing.org/articles/v008a014 Abstract -------- We present two algorithms for the approximate nearest neighbor problem in high-dimensional spaces. For data sets of size n living in 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.