Re: Multidimensional binary search trees

On Apr 17, 2:29 pm, king...@xxxxxxxxxxx wrote:
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.

kd-trees are good for nearest-neighbour queries in the approximate
sense. There's a paper on approximate nearest-neighbour searching
using kd-trees.

http://theory.stanford.edu/~rinap/papers/nnsqualpods.ps

Also look at this standard text-book description: -
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE188.HTM


thanks,
mayur

.

Relevant Pages

  • Re: K nearest neighbours
    ... Instead I can find classification stuff. ... for each point in a point set Q, find its k nearest ... neighbours. ... Yes kd-trees are a very good choice for your problem. ...
    (comp.graphics.algorithms)
  • Multidimensional binary search trees
    ... efficient search tree. ... to do is finding the nearest neighbour point (that is, ... If kd-trees are suitable for a multidimensional problem, ...
    (comp.theory)