Practical additions to kdtree library

[Willi Richert]

Hi,

being able to specify the dimensionality at run-time would be also desireable 
from the Python wrapper point of view. I am using the kdtree lib using my own 
SWIG generated Python wrappers. As such I have to created at the moment for 
every use case (dimensionality and data type) a special swig stub by hand. I 
really would appreciate if kdtree had some runtime parameter for that so that 
I could rewrite the kdetree.i in a more generic way.

In any case, if you need the wrappers, just mail me.

Regards,
wr

Am Dienstag 30 September 2008 09:15:29 schrieb 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/537f667f/attachment-0001.htm