Re: Nearest neighbours

Nicolas Bonneel wrote:
Please, don't do bruteforce (except if you do it on gpu...) - it will be
far too slow!!

I now know that it is the all-k-nearest-neighbors that I need. I have
implemented 4 algorithms:

1) Brute force
2) Axis-projection based
3) kd-tree (with sliding midpoing rule, exact matches)
4) All-nearest-neighbors algorithm

The 4) is from the paper:

http://tinyurl.com/ddfqke

My timing results indicate that the kd-tree outperforms all methods by
far. In the following I assume the point set consists of 10000 points
generated uniformly inside a hyperball.

Algorithm 4) has exponential dependence on dimension: already in
dimension 4 brute force outperforms this algorithm. In dimension 2 kd-
tree outperforms 4) by a factor of 4x. In dimension 3 the factor is
about 21x. In short, I wouldn't recommend it to anyone.

The only algorithms that adapt to higher dimensions are the kd-tree and
the brute force. Dimension 20 is no problem for either, taking brute
force 20 seconds, and kd-tree 31 seconds. Brute force algorithm
outperforms kd-tree from dimension 12 where the performances are nearly
equal. Take dimension 12 and vary point set size: then the performances
stay nearly equal (tested up to 20000 points). I didn't expect this.

While kd-tree has impressive adaptability, dimension 11 seems to be as
high as one can go with it. This leads me to believe that there does not
exist an algorithm that can answer exact nearest neighbor queries faster
than brute-force in dimensions >= 12. Thus my only hope for making those
higher dimensions faster is now on
1) approximate nearest neighbors queries, and
2) parallel computation

Parallel computation brings us to GPUs. Would you think that it is
possible to implement an n-dimensional kd-tree on a GPU and use it to
solve this problem?

--
http://kaba.hilvi.org
.

Relevant Pages

  • Re: Nearest neighbours
    ... Dimension 20 is no problem for either, taking brute force 20 seconds, and kd-tree 31 seconds. ... Brute force algorithm outperforms kd-tree from dimension 12 where the performances are nearly equal. ...
    (comp.graphics.algorithms)
  • Re: ratio approximation algorithm
    ... I'm looking for an algorithm other than brute force that ... >> will speed up the searching process. ... I'd be surprised if Monte Carlo failed to suit your needs. ... a pure brute force approach took 0.37 seconds on my laptop (1.8GHz ...
    (comp.programming)
  • Re: Bonehead basic crypto question
    ... Even if 256-bit is broken by brute force using quantum computers ... as is secure should be used. ... People might like to say "even if an algorithm is ... be conservative) and focus on eliminating shortcut attacks. ...
    (sci.crypt)
  • Re: Nearest neighbours
    ... ANN performs in about 8 seconds compared to my current kd-tree's 26 ... I just finished reading the paper which describes the algorithm ... their algorithm uses a data structure which is almost like ... a kd-tree, ...
    (comp.graphics.algorithms)
  • Re: Searching substrings in records.
    ...     for each text field in the record ... but I just can't tell the difference between the algorithm ... you introduced above and the brute force approach I described on the ... every record and perform a substring search on any of them. ...
    (comp.programming)