2
$\begingroup$

This post and this post indicate that when the dimensionality gets higher, KDTree gets slower.

Per scikit-learn doc, the KDTree becomes inefficient as D(dimensions) grows very large (say, $D>20$): this is one manifestation of the so-called “curse of dimensionality”.

Is there some theoretical verification or explanation of why KDTree gets slower when the dimensionality gets higher?

$\endgroup$
3
$\begingroup$

The problem arises due to curse of dimensionality. If the dimensionality is $k$ , the number of points in the data, $N$ should be $N ≫ 2^k$. Otherwise, when $k-d$ trees are used with high-dimensional data, most of the points in the tree will be evaluated and the efficiency is no better than brute force search. So for high value of $k$, approximate nearest-neighbour methods should be used instead.

most of the points in the tree will be evaluated

When the dimensionality increases to high value, the volume of the space increases so fast that the available data become sparse.Organizing and searching data often relies on detecting areas where objects form groups with similar properties; in high dimensional data, however, all objects appear to be sparse and dissimilar in many ways, which prevents common data organization strategies from being efficient. Hence $k-d$ trees become ineffiecient for high dimensions.

$\endgroup$
  • $\begingroup$ Thanks for your answer. In your context, what is the minimum value of $\dfrac{N}{2^k}$ $\endgroup$ – singularli Sep 24 '19 at 11:25
  • $\begingroup$ I don't think that the minimum value of $N/2^k$ can be defined. We just say that it should be large enough so that it doesn't become brute-force solution (for practical purposes). But you can safely assume it to be greater than $10$. Even this will give way better results than brute force. $\endgroup$ – tanmay_freak Sep 25 '19 at 17:27

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.