Performance of find methods, comparison with linear search

[Renaud Detry]

Hi all,

I ran a couple of performance tests on libkdtree (pulled on
Saturday). Experiments and results are attached, but the archive is
also published at

   http://www.montefiore.ulg.ac.be/~detryr/public/ 
kdtree_perf_test.tar.gz

in case the attachment doesn't go through.

 From these tests, it seems that

1.- libkdtree find-within-range becomes faster than "dumb" linear search
     when sets contain more than 1000 points. This doesn't take the tree
     construction overhead into account.

2.- libkdtree find-nearest is slower than linear search, at least
     for sets containing up to 100000 elements.

I am very surprised by (2) :-/. I would think that there's something
wrong in the way I do the test, but I can't find what...

Can anyone comment on these?

My personal interest in libkdtree is an optimized within-range search
through sets of 100 to 500 points. From the previous comparisons, it
seems that in this case libkdtree, and probably kdtrees in general,
are not a better solution than linear search. Does this sound fair to
you guys?

A bit of details on the test files:

kdtree_perf_test:
   Makefile
   Stopwatch.h
   data-100000probes-figs:
     non_optimized_vs_linear.loglog.pdf
     ...
   data-100000probes-sorted-asc-figs:
     non_optimized_vs_linear.loglog.pdf
     ...
   data-100000probes-sorted-asc.m
   data-100000probes.m
   script.sh
   test_kdtree.cpp

test_kdtree.cpp is adapted from libkdtree/examples/test_kdtree.cpp

script.sh calls test_kdtree several times to create the .m data files
and plots.

It's worth taking a look at
data-100000probes-figs/non_optimized_vs_linear.loglog.pdf

Two more remarks:

- I tried modifying _M_find_nearest to avoid functional recursion, by
   queuing "recursion jobs" in a fifo queue of elements of type

     struct find_state
     {
       find_state(_Link_type n, _Region b, size_t l) :
         n(n), b(b), l(l) {}
       _Link_type n; _Region b; size_t l;
     };

   This gave a small speedup (about .5). The same change in
   _M_find_within_range doesn't seem to make things any faster.

- I made the modest changes to _M_find_nearest to allow searching the p
   nearest elements. However, given the apparent performance of
   _M_find_nearest, this won't be of any help to me. If you like, I can
   send a patch tough.

Cheers,
Renaud.