<p>I implemented the UB tree. Despite the tree passes all tests from <code>ub_tree_test.cpp</code> including the test that verifies <code>MinDistance()</code> and <code>MaxDistance()</code>, <code>KNNTest/KNNModelTest</code> sometimes fails, I am trying to fix that.</p>

<p>The bound of the UB tree consists of a number of hyperrectangles in such a way that children of the UB tree do not overlap each other. However, I realized that the calculation of the distance between two nodes requires a lot of operations. So, I had to add some limitations on the number of hyperrectangles.</p>

<p>The tree sorts the dataset before the split process since the tree introduces an ordering in multidimensional space and all points are inserted into the tree according to that ordering. Probably it is better to choose a number of distinct samples and to split according the median. </p>

<hr>

<h4>You can view, comment on, or merge this pull request online at:</h4>
<p>&nbsp;&nbsp;<a href='https://github.com/mlpack/mlpack/pull/746'>https://github.com/mlpack/mlpack/pull/746</a></p>

<h4>Commit Summary</h4>
<ul>
  <li>Universal B tree implementation</li>
</ul>

<h4>File Changes</h4>
<ul>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-0">src/mlpack/core/tree/CMakeLists.txt</a>
    (5)
  </li>
  <li>
    <strong>A</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-1">src/mlpack/core/tree/address.hpp</a>
    (187)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-2">src/mlpack/core/tree/binary_space_tree.hpp</a>
    (1)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-3">src/mlpack/core/tree/binary_space_tree/traits.hpp</a>
    (17)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-4">src/mlpack/core/tree/binary_space_tree/typedef.hpp</a>
    (8)
  </li>
  <li>
    <strong>A</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-5">src/mlpack/core/tree/binary_space_tree/ub_tree_split.hpp</a>
    (64)
  </li>
  <li>
    <strong>A</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-6">src/mlpack/core/tree/binary_space_tree/ub_tree_split_impl.hpp</a>
    (301)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-7">src/mlpack/core/tree/bounds.hpp</a>
    (1)
  </li>
  <li>
    <strong>A</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-8">src/mlpack/core/tree/cellbound.hpp</a>
    (211)
  </li>
  <li>
    <strong>A</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-9">src/mlpack/core/tree/cellbound_impl.hpp</a>
    (803)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-10">src/mlpack/methods/neighbor_search/kfn_main.cpp</a>
    (14)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-11">src/mlpack/methods/neighbor_search/knn_main.cpp</a>
    (14)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-12">src/mlpack/methods/neighbor_search/ns_model.hpp</a>
    (6)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-13">src/mlpack/methods/neighbor_search/ns_model_impl.hpp</a>
    (6)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-14">src/mlpack/tests/CMakeLists.txt</a>
    (1)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-15">src/mlpack/tests/aknn_test.cpp</a>
    (16)
  </li>
  <li>
    <strong>M</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-16">src/mlpack/tests/knn_test.cpp</a>
    (12)
  </li>
  <li>
    <strong>A</strong>
    <a href="https://github.com/mlpack/mlpack/pull/746/files#diff-17">src/mlpack/tests/ub_tree_test.cpp</a>
    (334)
  </li>
</ul>

<h4>Patch Links:</h4>
<ul>
  <li><a href='https://github.com/mlpack/mlpack/pull/746.patch'>https://github.com/mlpack/mlpack/pull/746.patch</a></li>
  <li><a href='https://github.com/mlpack/mlpack/pull/746.diff'>https://github.com/mlpack/mlpack/pull/746.diff</a></li>
</ul>

<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">&mdash;<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/746">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFNoMQ_9WGzSpgjF4XfzAqVUmWaQ1ks5qbgm_gaJpZM4JZrEi">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFC_MIijW3Vl7QLl-jj_5C_alCYlEks5qbgm_gaJpZM4JZrEi.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/746"></link>
  <meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>