<div dir="ltr"><br><br><div class="gmail_quote">2008/9/30 Sylvain Bougerel <span dir="ltr"><<a href="mailto:sylvain.bougerel.devel@gmail.com">sylvain.bougerel.devel@gmail.com</a>></span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d">> 2008/9/30 Prabhanjan Kambadur <<a href="mailto:pkambadu@indiana.edu">pkambadu@indiana.edu</a>><br>
>><br>
>> Dear Sylvain and Paul,<br>
>><br>
>> Thank you for the interest. Just to clarify, I did not envision a KDTree<br>
>> that would change dimensionality on the fly. The use case would be more<br>
>> like:<br>
>><br>
>> KDTree<MyCoordinateType> my_tree;<br>
>> my_tree.set_dimension(3);<br>
>> // use the tree<br>
>> my_tree.wipe();<br>
>> my_tree.set_dimension(5);<br>
>> // use it again.<br>
>><br>
>> Here, MyCoordinateType can be dynamically reconfigured. Of course, the<br>
>> method names could be more fitting :-). The reason I mention this is because<br>
>> we use the KDTree as a primary data structure in the library. We support<br>
>> reconfiguring our library through a similar mechanism. Being a staunch<br>
>> supporter of the generic programming paradigm, I am all for compile-time<br>
>> polymorphism. At the same time, I have been convinced by the scientists we<br>
>> work with at the IBM T J Watson Research Center that the dimensionality<br>
>> really is a feature of the data set, and as such, should be a runtime<br>
>> parameter (in this particular case at least).<br>
<br>
</div>I'm also convienced the dimensionality is a feature of the data set.<br>
But, humm, generally the dimensionality of the data set is known at<br>
compile time. However, I do understand why you need such a feature, or<br>
rather why the scientist have requested it. Moreover, if we follow the<br>
conversation, we can assume that you do have a lot of modification of<br>
your data set.<br>
</blockquote><div><br><br>my dataset ?<br><br>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.<br>
<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>
This is a rather particular use case. Indeed, the first request of<br>
this type I have seen. Well, there is two ways of approaching the<br>
problem.<br>
<br>
1. Creating a polymorphic wrapper for D in '[a, b]', and generating<br>
all the necessary Kd-tree<D>. Not elegant, slower and bulky (lot's of<br>
code generated), plus need 'a' and 'b' to be known.</blockquote><div><br>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.<br>
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>
2. Modifying the source code of the Kd-tree. The most elegant solution.<br>
</blockquote><div><br>and it'll improve kdtree IMO, so that is a good byproduct.<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
Funnily enough, I can't find anything that would do the job for you in<br>
memory (without going through the hassle of a database).<br>
<div class="Ih2E3d"></div></blockquote><div><br>huh.<br><br>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.<br>
<br>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.<br><br>
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="Ih2E3d"><br>
<br>
>><br>
>> Actually, one could support setting the dimension both at compile-time and<br>
>> at run-time. For example, one can imagine partial specialization of the<br>
>> KDTree for a particular sentinel value of dimension.<br>
<br>
</div>Okay, supporting both implementation.<br>
<br>
It's possible. But rather than a sentinel, I would prefer an explicit<br>
name. Since some function will be shared, but not many, obviously,<br>
both tree could stem from a sealed base class kdtree_base.<br>
</blockquote><div><br>they could. or we could just use a template typedef (in the future) or something like this for now:<br>template <etc etc><br>struct kdtree_mutable<br>{<br> typedef kdtree<sentinel,etc etc> type;<br>
}<br><br>then your mutable looks like<br>kdtree_mutable<etc etc>::type tree;<br> <br><br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
Something like a "mutable_kdtree" could be reconfigured on the fly.<br>
There would not even be a need to "clean" the tree before actually...<br>
another tree could be created from within the "dimension" method, all<br>
the elements inserted, then both trees content would be swapped.<br>
</blockquote><div><br>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.<br>
</div>see ya<br>Paul<br></div><br></div>