Many real-world objects can be naturally modeled as high- dimensional vectors. For example, a 1000x1000 image can be modeled as a vector in 1,000,000-dimensional space. Searching for pairs of close vectors enables finding pairs of
similar objects. However, the exhaustive search (enumerating all pairs of vectors to discover the close ones) is often intractable.

The new approach by Andoni and Indyk yields a much faster solution for this problem. It uses a decomposition of the search space using grids of balls. On the picture mounted above, a decomposition for two-dimensional space is shown. Pairs of close points are more likely to have the same color than points that are far apart.

The picture immediately below, illustrates a partial decomposition in three dimensions.

Some of the methods and applications of Locality Sensitive Hashing (LSH) to learning and vision are featured in

http://people.csail.mit.edu/gregory/annbook/book.html

The detailed description of the LSH methods can be found at:

http://web.mit.edu/andoni/www/LSH/index.html