MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
You can use HEngine algorithm. – mrgloom Feb 26 '14 at 6:29

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.

share|cite|improve this answer
Hi Joseph, thanks for your reply! Indeed, I'm familiar with the LSH concept. Their bounds are nice, but still a bit too strict for my particular problem. I've been away from the field during this last decade, and I was hoping there had been further developments. cheers – pedritolo1 Nov 27 '12 at 13:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.