fast approximate k-nearest neighbors in high dimensions?

Question

Hi, I've been scanning the literature trying to find an adequate approximate k-neighbour for my outlandish data set, but I remain stymied. Perhaps someone can help?

The dataset is huge, both in cardinality and in the number of dimensions, although the former is orders of magnitude higher than the latter. The vectors are of binary values, and we're minimizing the Hamming distance. Let's assume I've already done the obvious procedures, such as the typical techniques for dimensionality reduction, random sampling a subset, etc, and I'm now dealing with what's left. Which is still gigantic.

Formally, let T be the training data set (subset of in {0,1}^d) and n the cardinality #T.

For the training phase, the algorithm mustn't exceed o(d*n) for complexity and storage (give or take some extra Log factors). For the classification phase, complexity shouldn't exceed o(ln(n)*d). I'm well aware that with such stringent requirements, the approximate solution can't be very good. I can live with that.

thanks all for your time! cheers

Answer 1

Do you know this seminal paper, which Google Scholar shows has been cited 1438 times in the past 13 years?

Piotr Indyk and Rajeev Motwani, "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality," 1999, ACM link:

"we obtain the first known algorithm with polynomial preprocessing and query time polynomial in $d$ and $\log n$," where $d$ is the dimension and $n$ is the number of points.

Later Piotr wrote a summary chapter in the Handbook of Discrete and Computational Geometry, "Nearest Neighbors In High-Dimensional Spaces," 2004, Citeseer link.