3
$\begingroup$

I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also I've read that in general, all space-partitioning data structures tends to perform exhaustive search with high dimensional data.

Additionally, there are two important facts to be considered (ordered by relevance):

  • Precision: The nearest neighbors must be found (not approximations).
  • Speed: The search must be as fast as possible. (The time to create the data structure isn't really important).

So, I need some advice about:

  1. The data structure to perform kNN.
  2. If it will be better to use an aNN (approximate nearest neighbor) approach, setting it as accurate as possible?.
$\endgroup$
1
$\begingroup$

Here is a closely related question (although different enough that I wouldn't call this a duplicate): https://stackoverflow.com/questions/5751114/nearest-neighbors-in-high-dimensional-data

As you said, all known structures degrade to linear search as the dimension grows. More specifically, the efficiency degrades as the dimension approached the number of points in the feature space (binary search doesn't help with two points, K-D trees are useless on three points, etc.).

However, if the time to create the data structure does not matter at all, you can create a complete graph with sorted edge lists. That is, every node keeps track of its neighbors in nearness order. This would take $O(n^2 \log n)$ time to create, but would give you the kNN of any point in $O(1)$.

$\endgroup$
  • $\begingroup$ I don't see how this graph would give $O(1)$ for a neighbor search. Let $P_0$ be a test point (not in the training set), then this structure doesn't seems useful. $\endgroup$ – mavillan Aug 22 '15 at 17:26
  • $\begingroup$ @mavillan You are right. This only helps with already existing points. I do not know of a non-approximate method to find kNN of new points in sublinear time. $\endgroup$ – Kittsil Aug 22 '15 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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