Practical additions to kdtree library

[Paul Harris]

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

> > 2008/9/30 Prabhanjan Kambadur <pkambadu at indiana.edu>
> >>
> >> Dear Sylvain and Paul,
> >>
> >> Thank you for the interest. Just to clarify, I did not envision a KDTree
> >> that would change dimensionality on the fly. The use case would be more
> >> like:
> >>
> >> KDTree<MyCoordinateType> my_tree;
> >> my_tree.set_dimension(3);
> >> // use the tree
> >> my_tree.wipe();
> >> my_tree.set_dimension(5);
> >> // use it again.
> >>
> >> Here, MyCoordinateType can be dynamically reconfigured. Of course, the
> >> method names could be more fitting :-). The reason I mention this is
> because
> >> we use the KDTree as a primary data structure in the library. We support
> >> reconfiguring our library through a similar mechanism. Being a staunch
> >> supporter of the generic programming paradigm, I am all for compile-time
> >> polymorphism. At the same time, I have been convinced by the scientists
> we
> >> work with at the IBM T J Watson Research Center that the dimensionality
> >> really is a feature of the data set, and as such, should be a runtime
> >> parameter (in this particular case at least).
>
> I'm also convienced the dimensionality is a feature of the data set.
> But, humm, generally the dimensionality of the data set is known at
> compile time. However, I do understand why you need such a feature, or
> rather why the scientist have requested it. Moreover, if we follow the
> conversation, we can assume that you do have a lot of modification of
> your data set.
>


my dataset ?

oh, I had nearly forgotten about backwards compatibility.  the new kdtree
will have to support the old <N> templated dimensions... either that or
break kdtree so that users can easily find and fix problems in their code.



>
> This is a rather particular use case. Indeed, the first request of
> this type I have seen. Well, there is two ways of approaching the
> problem.
>
> 1. Creating a polymorphic wrapper for D in '[a, b]', and generating
> all the necessary Kd-tree<D>. Not elegant, slower and bulky (lot's of
> code generated), plus need 'a' and 'b' to be known.


that is a possible solution.  check out boost's preprocessor library for
easy ways of generating 1..N copies of similar code.  still, its a hassle.


>
> 2. Modifying the source code of the Kd-tree. The most elegant solution.
>

and it'll improve kdtree IMO, so that is a good byproduct.


>
> Funnily enough, I can't find anything that would do the job for you in
> memory (without going through the hassle of a database).
>

huh.

well, when you guys start using it, please also benchmark kdtree... we've
managed to improve its performance in the past, and I'm sure theres more
performance that could be squeezed out.

i came involved in kdtree when i wasn't happy with the way it erased
elements in the tree... maybe your crowd can contribute something too?  if
not code, then a real-world setting to test and validate kdtree.



>
>
> >>
> >> Actually, one could support setting the dimension both at compile-time
> and
> >> at run-time. For example, one can imagine partial specialization of the
> >> KDTree for a particular sentinel value of dimension.
>
> Okay, supporting both implementation.
>
> It's possible. But rather than a sentinel, I would prefer an explicit
> name. Since some function will be shared, but not many, obviously,
> both tree could stem from a sealed base class kdtree_base.
>

they could.  or we could just use a template typedef (in the future) or
something like this for now:
template <etc etc>
struct kdtree_mutable
{
  typedef kdtree<sentinel,etc etc> type;
}

then your mutable looks like
kdtree_mutable<etc etc>::type tree;




> Something like a "mutable_kdtree" could be reconfigured on the fly.
> There would not even be a need to "clean" the tree before actually...
> another tree could be created from within the "dimension" method, all
> the elements inserted, then both trees content would be swapped.
>

I suppose we could always swap the tree contents from one tree to another,
and run an optimise() / optimize().  that would resort the tree according to
the new tree's accessor and dimensionality.

see ya
Paul
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20080930/3aa73e60/attachment.htm