<div dir="ltr">Hi Sebastien and others,<div><br></div><div>I will retry with the new addresses.</div><div><br></div><div>The real reason why I wanted the latest sources was to do performance comparisons between libkdtree++ and spatial (<a href="https://sourceforge.net/projects/spatial/">https://sourceforge.net/projects/spatial/</a>).</div>
<div><br></div><div>During the course of the performance comparisons, I insert 1000000 points in 3 or 9 dimensions and watch how the 2 libraries behave, on insertion and insertion with optimization.</div><div><br></div><div>
This has lead me to the discovery of one bug very important bug and its fix. Spatial originally (a year ago) suffered from the same issue, so I was able to identify it quickly.</div><div><br></div><div>In the KDTree::_M_optimize, the body in the version I have is:</div>
<div><br></div><div><div> template <typename _Iter></div><div> void</div><div> _M_optimise(_Iter const& __A, _Iter const& __B,</div><div> size_type const __L)</div><div>
{</div><div> if (__A == __B) return;</div><div> _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);</div><div> _Iter __m = __A + (__B - __A) / 2;</div><div> std::nth_element(__A, __m, __B, compare);</div>
<div> this->insert(*__m);</div><div> if (__m != __A) _M_optimise(__A, __m, __L+1);</div><div> if (++__m != __B) _M_optimise(__m, __B, __L+1);</div><div> }</div></div><div><br></div><div>But it should be:</div>
<div><br></div><div><div><div> template <typename _Iter></div><div> void</div><div> _M_optimise(_Iter const& __A, _Iter const& __B,</div><div> size_type const __L)</div>
<div> {</div><div> if (__A == __B) return;</div><div> _Node_compare_ compare(__L % __K, _M_acc, _M_cmp);</div><div> _Iter __m = __A + (__B - __A) / 2;</div><div> std::partial_sort(__A, __m, __B, compare);</div>
<div> this->insert(*__m);</div><div> if (__m != __A) _M_optimise(__A, __m, __L+1);</div><div> if (++__m != __B) _M_optimise(__m, __B, __L+1);</div><div> }</div></div></div><div><br></div><div>
(notice the change from std::nth_element to std::partial_sort)</div><div><br></div><div>Using nth_element here is a erroneous, because it does not guarantee that everything in the sequence [__A, __m) is lower than _m nor that everything in the sequence (__m, __B] is greater than __m. This is expected from the algorithm because it operates on a subset where the point sorted along the dimension __L % __K are strictly ordered around the pivot __m.</div>
<div><br></div><div>In practice nth_element does "some" sorting around the pivot __m and this bug was not noticeable when inserting less than 10,000 elements. I started to get different results between some random nearest neighbor queries at 10,000 elements. At 1,000,000 elements, efficient_insert_and_optimize started to crash with Segmentation Faults on Linux.</div>
<div><br></div><div><div>Replacing nth_element by partial_sort fixes the issues described above, because partial_sort enforces the guarantee needed here.</div></div><div><br></div><div>If the current maintainers agree with the proposed changes, I'd like to request their good will to apply the changes on my behalf in the source. To top it off, I think, a long time ago (5 years may be?), I may have been the one proposing to replace a previous std::sort by std::nth_element (I remember a conversation with Paul on this)... So I might even have introduced the bug in the first place :(</div>
<div><br></div><div>According to my current experiments, at the moment libkdtree++ cannot be assumed to maintain its invariant throughout the tree after a call to _M_optimize(). If you are a user of optimization in libkdtree++ with large data sets, then you have probably experienced this issue, if the code above is the one you are using.</div>
<div><br></div><div>Best Regards,</div><div>Sylvain</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sun, Nov 24, 2013 at 9:41 PM, Sebastian Ramacher <span dir="ltr"><<a href="mailto:sebastian+lists@ramacher.at" target="_blank">sebastian+lists@ramacher.at</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On 2013-11-24 21:20:25, Sylvain Bougerel wrote:<br>
> Thank you Sebastien, I will wait a bit then.<br>
<br>
</div>It should be back up:<br>
<a href="https://lists.debian.org/debian-infrastructure-announce/2013/11/msg00002.html" target="_blank">https://lists.debian.org/debian-infrastructure-announce/2013/11/msg00002.html</a><br>
<br>
Regards<br>
<span class="HOEnZb"><font color="#888888">--<br>
Sebastian Ramacher<br>
</font></span><br>_______________________________________________<br>
libkdtree-devel mailing list<br>
<a href="mailto:libkdtree-devel@lists.alioth.debian.org">libkdtree-devel@lists.alioth.debian.org</a><br>
<a href="http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/libkdtree-devel" target="_blank">http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/libkdtree-devel</a><br></blockquote></div><br></div>