Performance of find methods, comparison with linear search

[V.P. Dinh]

I'm following this discussion for a while now cause I'm in the
decision process of whether to use the library for a new project. I'm
having a two dimensional space only (points on the ground) and need to
find points within a certain range, but this for like 80.000 points
and in real time. Wondering whether the library is fast enough for
that? (I'm working on an occupancy grid by the way, for people from
the robotics field).

On Nov 5, 2007 1:33 AM, Renaud Detry <renaudjdetry at airpost.net> wrote:
> 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.
>
>
> _______________________________________________
> libkdtree-devel mailing list
> libkdtree-devel at lists.alioth.debian.org
> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>



-- 
Relationship getting boring? Spice it up with our sexy lingerie.
http://www.romanceculture.com