Efficient search for approximate nearest neighbor in high dimensional spaces

We address the problem of designing data structures that allow efficient se arch for approximate nearest neighbors. More specifically given a database consisting of a set of vectors in some high dimensional Euclidean space, we want to construct a space-efficient data structure that would allow us to search, given a query vector, for the closest or nearly closest vector in t he database. We also address this problem when distances are measured by th e L-1 norm and in the Hamming cube. Significantly improving and extending r ecent results of Kleinberg, we construct data structures whose size is poly nomial in the size of the database and search algorithms that run in time n early linear or nearly quadratic in the dimension. (Depending on the case, the extra factors are polylogarithmic in the size of the database.).