Practical additions to kdtree library

Sylvain Bougerel sylvain.bougerel.devel at gmail.com
Tue Sep 30 02:04:49 UTC 2008


Hi,

Well, I don't think this is the goal of the library. AFAIK, there is
no such kd-tree that can change the dimensionality on the fly. The
reason for this is: the KD-tree invariant is based on the number of
dimensions. Changing the number of dimension is equivalent to
repopulate the entire Kd-tree.

The force of this library, however, lies in the fact that we do not
rebuild the entire tree when we change the set of data. We just
add/remove one element to the tree. So this library makes sense if you
have a lot of modifications going on in your data set.

If you are only looking for nearest neighbor search performance, and
your data is not being modified very often, I recommend you to use
either ANN, or CGAL's kd-tree. They only build the kd-tree to reply to
the nearest neighbor query, and, at the time of the query, you will
most likely know exactly how many dimensions you'll be working with.

Hope this helps.

Cheers,

Sylvain

On Fri, Sep 26, 2008 at 2:55 AM, Prabhanjan Kambadur
<pkambadu at indiana.edu> wrote:
> Dear Authors,
>
> Firstly, let me apologize for the lengthy mail.
>
> We (Indiana University and IBM) have a generic parallel library (PFunc) that
> will be open sourced in the near future. Being generic, it allows users to
> plug in different components. One such component of our generic library are
> the queues used to manage tasks. We have users who want to use KDTrees for
> their task queue management. This allows them to execute tasks which are
> nearest neighbors of the previous tasks. We have found that your
> implementation is very thorough and easy to understand, and as such are
> happy to recommend our users to use. However, some users have complained
> about the lack of a particular feature.
>
> Your KDTree implementation pegs the dimensionality of the tree at compile
> time. While I understand the reasons for doing so (my background is in
> generic programming as well), it inhibits from users to dynamically change
> the dimensionality. As a simple example of why this might be required,
> consider weather modeling. Depending of what needs to be modeled (pressure,
> humidity, etc), the dimensionality of the data changes. As you can see, your
> current KDTree implementation does not allow for this.
>
> Is there some way of changing this?
>
> Please let me know,
>
> Anju
>
>
>
> _______________________________________________
> libkdtree-devel mailing list
> libkdtree-devel at lists.alioth.debian.org
> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>
>



More information about the libkdtree-devel mailing list