Performance of find methods, comparison with linear search
Renaud Detry
renaudjdetry at airpost.net
Mon Nov 5 12:46:30 UTC 2007
Hello Sylvain,
> Some more details than the previous mail. Oh, I can't access the link.
> "you don't have the permission"...
Yes, the link got cut somehow. You need to enter the complete url
http://www.montefiore.ulg.ac.be/~detryr/public/kdtree_perf_test.tar.gz
up to the .tar.gz.
>> 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?
>
> Honestly, I don't know for 100 to 500 points. But it really seems to
> me that linear search should be the slowest, especially if your range
> is small.
Yes, that was my feeling as well. However, I am not able to confirm
it in practice. Maybe the kdtree has some side effects, like
eating more proc cache... This could explain the overhead for smaller
point sets...
Renaud.
More information about the libkdtree-devel
mailing list