libkdtree vs. BKD-Tree

Willi Richert richert at
Wed Apr 23 12:06:35 UTC 2008


exactly. I will provide a C++-file in which one has to define fixed types. 
Using the Makefile it will then be no problem to generate the custom KDTree 
lib for Python.

On Wednesday, 23. April 2008 11:15:04 Paul Harris wrote:
> On 23/04/2008, Willi Richert <richert at> wrote:
> > Hi,
> >
> > thanks for the view. Do you then actually use the "logarithmic method" as
> > proposed by the BKD authors? I mean, they claim in their paper to
> > guarantee
> > amortized log time operations (insert, remove, find). As your code looks
> > much
> > cleaner and shorter to me  I wonder which other method besides BKD you
> > use to
> > maintain that guarantee. How costly actually is the rebalancing
> > subsequent to
> > insert/remove?
> i didn't read that much in depth actually, so i can't comment on the log
> method.  and sorry but its been a while since i've read the code to comment
> on the rebalancing costs.  lets see if someone else says something on that.
> i forgot to CC the list, i remembered this time.
> The next days I will examine how I could wrap it in Python. If someone is
> > interested please let me know.
> i am not personally interested, but more exposure would also help to
> increase the user base and thus the developer base.
> one key part of libkdtree is that it is heavy on templates, so i assume
> you'd have to specify a fixed set of datatypes and accessors for the python
> wrapper?


Dipl.-Inform. Willi Richert
C-LAB - Cooperative Computing & Communication Laboratory
 der Universität Paderborn und Siemens

Fürstenallee 11
D-33102 Paderborn
Tel: +49 5251 60 6120
Fax: +49 5251 60 6165

More information about the libkdtree-devel mailing list