Efficient search for approximate nearest neighbor in high dimensional spaces

Abstract

We address the problem of designing data structures that allow efficient search 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 struct,ure t,hat would allow us to search, given a query vector, for t.he closest or nearly closest vector in the database. We also address t.hii problem when distances are measured by the L1 norm, and in t.he Hamming cube. Sign%cant.ly improving and extending recent results of Kleinberg, we const,ruct data structures whose size is polynomial in the size of t,he database, and search algorithms t,hat run in time nearly linear or nearly quadratic in the dimension (depending on the case; the extra factors are polylogarit.hmic in the size of the database). 1 Introduction Motivation.