title: Why k-d trees is not used for high dimensional data?
body: <p>Quoting Wikipedia on k-d tree's page:</p>
  
  <blockquote>
    <p>k-d trees are not suitable for efficiently finding the nearest
    neighbour in high-dimensional spaces. As a general rule, if the
    dimensionality is k, the number of points in the data, N, should be N>>
     2k. 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 exhaustive search,[11] and approximate
    nearest-neighbour methods should be used instead.</p>
  </blockquote>
  
  <p>I don't understand the difference between the dimensionality (k) and the number of points in the data (N) and why it's true the statement about when k-d trees are not convenient.</p>