<p>I think the Hilbert R tree is almost done and it's time to make PR.</p>
<p>Known issues:<br>
1. I am not sure of the <code>DiscreteHilbertValue</code> class. It uses <code>std::list</code> for the local dataset.<br>
<code>std::list<arma::Col<uint64_t>> *localDataset;</code><br>
I think <code>std::vector</code> or <code>arma::Mat</code> may be much faster since <code>std::list</code> can not reserve memory.<br>
And maybe the type of the <code>arma::Col</code> should be a template parameter.<br>
2. The RecursiveHilbertValue class is very slow. I think it is better to utilize at each step at least 32 bits instead of one.<br>
3. Some constructions like <code>root->AuxiliaryInfo().LargestHilbertValue().LargestValue()</code> are long. As for me it is better to correct them.</p>
<p>Now the tree passes RectangleTreeTest/(DiscreteHilbertRTreeTraverserTest, RecursiveHilbertRTreeTraverserTest, DiscreteHilbertOrderingTest, RecursiveHilbertOrderingTest) tests. I'll try to think out other tests.</p>
<hr>
<h4>You can view, comment on, or merge this pull request online at:</h4>
<p> <a href='https://github.com/mlpack/mlpack/pull/664'>https://github.com/mlpack/mlpack/pull/664</a></p>
<h4>Commit Summary</h4>
<ul>
<li>Added initial support for Hilbert R trees (split and descent heuristic design).</li>
<li>Move tree-specific information to a new class (AuxiliaryInformationType).</li>
<li>A lot of changes. Implemented two approaches in order to compare points.</li>
<li>Added a bit of documentation.</li>
<li>Hilbert R tree fixes.</li>
</ul>
<h4>File Changes</h4>
<ul>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-0">src/mlpack/core/tree/CMakeLists.txt</a>
(12)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-1">src/mlpack/core/tree/rectangle_tree.hpp</a>
(7)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-2">src/mlpack/core/tree/rectangle_tree/discrete_hilbert_value.hpp</a>
(200)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-3">src/mlpack/core/tree/rectangle_tree/discrete_hilbert_value_impl.hpp</a>
(399)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-4">src/mlpack/core/tree/rectangle_tree/dual_tree_traverser.hpp</a>
(7)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-5">src/mlpack/core/tree/rectangle_tree/dual_tree_traverser_impl.hpp</a>
(16)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-6">src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_auxiliary_information.hpp</a>
(119)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-7">src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_auxiliary_information_impl.hpp</a>
(177)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-8">src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_descent_heuristic.hpp</a>
(59)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-9">src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_descent_heuristic_impl.hpp</a>
(59)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-10">src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_split.hpp</a>
(85)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-11">src/mlpack/core/tree/rectangle_tree/hilbert_r_tree_split_impl.hpp</a>
(334)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-12">src/mlpack/core/tree/rectangle_tree/no_auxiliary_information.hpp</a>
(84)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-13">src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic.hpp</a>
(13)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-14">src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic_impl.hpp</a>
(9)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-15">src/mlpack/core/tree/rectangle_tree/r_star_tree_split.hpp</a>
(24)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-16">src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp</a>
(35)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-17">src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic.hpp</a>
(13)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-18">src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp</a>
(7)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-19">src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp</a>
(29)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-20">src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp</a>
(44)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-21">src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp</a>
(18)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-22">src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp</a>
(336)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-23">src/mlpack/core/tree/rectangle_tree/recursive_hilbert_value.hpp</a>
(227)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-24">src/mlpack/core/tree/rectangle_tree/recursive_hilbert_value_impl.hpp</a>
(245)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-25">src/mlpack/core/tree/rectangle_tree/single_tree_traverser.hpp</a>
(7)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-26">src/mlpack/core/tree/rectangle_tree/single_tree_traverser_impl.hpp</a>
(16)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-27">src/mlpack/core/tree/rectangle_tree/traits.hpp</a>
(7)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-28">src/mlpack/core/tree/rectangle_tree/typedef.hpp</a>
(40)
</li>
<li>
<strong>A</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-29">src/mlpack/core/tree/rectangle_tree/x_tree_auxiliary_information.hpp</a>
(158)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-30">src/mlpack/core/tree/rectangle_tree/x_tree_split.hpp</a>
(62)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-31">src/mlpack/core/tree/rectangle_tree/x_tree_split_impl.hpp</a>
(94)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/664/files#diff-32">src/mlpack/tests/rectangle_tree_test.cpp</a>
(145)
</li>
</ul>
<h4>Patch Links:</h4>
<ul>
<li><a href='https://github.com/mlpack/mlpack/pull/664.patch'>https://github.com/mlpack/mlpack/pull/664.patch</a></li>
<li><a href='https://github.com/mlpack/mlpack/pull/664.diff'>https://github.com/mlpack/mlpack/pull/664.diff</a></li>
</ul>
<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">—<br />You are receiving this because you are subscribed to this thread.<br />Reply to this email directly, <a href="https://github.com/mlpack/mlpack/pull/664">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe/AJ4bFPhU57acaI6bpl-9HX57FNj6W9zsks5qHZOUgaJpZM4IrlzT">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFApglGqONXtDLzwq_KJw8qGRhaEiks5qHZOUgaJpZM4IrlzT.gif" width="1" /></p>
<div itemscope itemtype="http://schema.org/EmailMessage">
<div itemprop="action" itemscope itemtype="http://schema.org/ViewAction">
<link itemprop="url" href="https://github.com/mlpack/mlpack/pull/664"></link>
<meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>