Practical additions to kdtree library

[Paul Harris]

2008/9/30 Sylvain Bougerel <sylvain.bougerel.devel at gmail.com>

> 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.
>

I don't think that Anju wanted to change it on the fly.  Maybe just at
initialisation time ?  eg

KDTree<Node> tree(5);   // for 5 dimensions

I think this is doable, but it means taking the template parameter and
converting it into a variable stored in the class.

Sorry I haven't been swift in pursuing this possibility, but off top of head
i think it is achievable.

What do you think Sylvain?



> 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
> >
> >
>
> _______________________________________________
> libkdtree-devel mailing list
> libkdtree-devel at lists.alioth.debian.org
> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20080930/aec234b2/attachment.htm