<p>In <a href="https://github.com/mlpack/mlpack/pull/747#discussion_r74254035">src/mlpack/core/tree/spill_tree/spill_tree_impl.hpp</a>:</p>
<pre style='color:#555'>> + }
> +
> + std::vector<size_t> leftPoints, rightPoints;
> + // Split the node.
> + overlappingNode = SplitPoints(tau, rho, points, leftPoints, rightPoints);
> +
> + // We don't need the information in points, so lets clean it.
> + std::vector<size_t>().swap(points);
> +
> + // Now we will recursively split the children by calling their constructors
> + // (which perform this splitting process).
> + left = new SpillTree(this, leftPoints, tau, maxLeafSize, rho);
> + right = new SpillTree(this, rightPoints, tau, maxLeafSize, rho);
> +
> + // Update count number, to represent the number of descendant points.
> + count = left->NumDescendants() + right->NumDescendants();
</pre>
<p>I think there is an easier way to do this. We only hold a list of point indices in the leaves, so we only have to worry about the arrangement of points at the leaf level. Each leaf node only has one sibling, so given two sibling leaf nodes N_l and N_r, let's define a couple sets. I've just chosen arbitrary set names:</p>
<ul>
<li>S: all the points held in N_l and N_r</li>
<li>T: points held in N_r but <em>not</em> in N_l</li>
<li>U: points held in both N_l and N_r</li>
<li>V: points held in N_l</li>
</ul>
<p>Now we can arrange the point sets for each child like this:</p>
<ul>
<li>N_l: <a href="order%20does%20not%20matter%20here">V</a>
</li>
<li>N_r: T U</li>
</ul>
<p>If we have set the number of descendants in the parent properly to be |S| (this should be easy), then we can do the following:</p>
<pre><code>size_t Descendant(const size_t i)
{
// Are we a leaf?
if (IsLeaf())
return (*pointsIndex)[index];
if (i > left->NumDescendants())
return left->Descendant(i);
else
return right->Descendant(i - left->NumDescendants());
}
</code></pre>
<p>The key to this approach is determining the sets T and U, but I think that is straightforward to do either before you recurse into building the children (you can "pre-organize" the set you pass to the right child), or afterwards (you can access the sets of the left and right child and organize them).</p>
<p>When you set <code>numDescendants</code> when building a node, that would simply be equal to the number of points held in that node. This means for a given node, it is possible (and okay) if <code>node->NumDescendants() < node->Left()->NumDescendants() + node->Right()->NumDescendants()</code>.</p>
<p>Let me know if I have overlooked anything here.</p>
<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/747/files/a71b57caa90311f5542180bc0553449c3691395d#r74254035">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFFJU_QfR4SotS5wiqfHUZlSVn5Yxks5qed8mgaJpZM4JZzLU">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFIY4c1Plp1ZDamZI3Ng9wo8Un8pOks5qed8mgaJpZM4JZzLU.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/747/files/a71b57caa90311f5542180bc0553449c3691395d#r74254035"></link>
<meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>
<script type="application/json" data-scope="inboxmarkup">{"api_version":"1.0","publisher":{"api_key":"05dde50f1d1a384dd78767c55493e4bb","name":"GitHub"},"entity":{"external_key":"github/mlpack/mlpack","title":"mlpack/mlpack","subtitle":"GitHub repository","main_image_url":"https://cloud.githubusercontent.com/assets/143418/17495839/a5054eac-5d88-11e6-95fc-7290892c7bb5.png","avatar_image_url":"https://cloud.githubusercontent.com/assets/143418/15842166/7c72db34-2c0b-11e6-9aed-b52498112777.png","action":{"name":"Open in GitHub","url":"https://github.com/mlpack/mlpack"}},"updates":{"snippets":[{"icon":"PERSON","message":"@rcurtin in #747: I think there is an easier way to do this. We only hold a list of point indices in the leaves, so we only have to worry about the arrangement of points at the leaf level. Each leaf node only has one sibling, so given two sibling leaf nodes N_l and N_r, let's define a couple sets. I've just chosen arbitrary set names:\r\n\r\n - S: all the points held in N_l and N_r\r\n - T: points held in N_r but _not_ in N_l\r\n - U: points held in both N_l and N_r\r\n - V: points held in N_l\r\n\r\nNow we can arrange the point sets for each child like this:\r\n\r\n - N_l: [V] (order does not matter here)\r\n - N_r: [T U] (order does matter: all points in T come before all points in U)\r\n\r\nIf we have set the number of descendants in the parent properly to be |S| (this should be easy), then we can do the following:\r\n\r\n```\r\nsize_t Descendant(const size_t i)\r\n{\r\n // Are we a leaf?\r\n if (IsLeaf())\r\n return (*pointsIndex)[index];\r\n\r\n if (i \u003e left-\u003eNumDescendants())\r\n return left-\u003eDescendant(i);\r\n else\r\n return right-\u003eDescendant(i - left-\u003eNumDescendants());\r\n}\r\n```\r\n\r\nThe key to this approach is determining the sets T and U, but I think that is straightforward to do either before you recurse into building the children (you can \"pre-organize\" the set you pass to the right child), or afterwards (you can access the sets of the left and right child and organize them).\r\n\r\nWhen you set `numDescendants` when building a node, that would simply be equal to the number of points held in that node. This means for a given node, it is possible (and okay) if `node-\u003eNumDescendants() \u003c node-\u003eLeft()-\u003eNumDescendants() + node-\u003eRight()-\u003eNumDescendants()`.\r\n\r\nLet me know if I have overlooked anything here."}],"action":{"name":"View Pull Request","url":"https://github.com/mlpack/mlpack/pull/747/files/a71b57caa90311f5542180bc0553449c3691395d#r74254035"}}}</script>