Multidimensional binary search trees

Hi,

i've a set S of points in R^n (a vector of n real numbers, where n, in
pratical applications, is between 10 and 60). The number of points is
in the order of 10^5, 10^6. I would like organize the points in an
efficient search tree. The most important operation that i would like
to do is finding the nearest neighbour point (that is, give a point
P=(a1,...,ak), tell me which is the first m nearest points in the set
S to P). P does not necessarely belong to S.

For n=2,3 i know that there are quadtrees and octrees. For k>3 i've
read about kd-trees, but i'm not sure if k represents the
dimensionality of the points (that is, k = n) or the number of points
per node...

If kd-trees are suitable for a multidimensional problem, are they
efficient? Are there any other data structures that i can use to solve
the problem?
Thank you.

.

Relevant Pages

  • Re: Multidimensional binary search trees
    ... pratical applications, ... to do is finding the nearest neighbour point ... ... If kd-trees are suitable for a multidimensional problem, ... The article catalogs dozens of data structures and notes which are ...
    (comp.theory)
  • Re: Multidimensional binary search trees
    ... P=, tell me which is the first m nearest points in the set ... If kd-trees are suitable for a multidimensional problem, ... There's a paper on approximate nearest-neighbour searching ...
    (comp.theory)