<p>In <a href="https://github.com/mlpack/mlpack/pull/747#discussion_r74244401">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>Hi,<br>
I think this is a complicated problem. I have been thinking about it for a while.<br>
The problem is this:<br>
Suppose we have a overlapping node N with 2 children: N<sub>1</sub> and N<sub>2</sub>.<br>
As N<sub>1</sub> and N<sub>2</sub> share some data points, we know that:</p>
<p>N<sub>1</sub>.NumDescendants() + N<sub>2</sub>.NumDescendants() > N.NumDescendants()</p>
<p>We want to avoid keeping a list of indexes for each non-leaf node. So, we want to access the:<br>
<code>[0, N.NumDescendants())</code> set of descendants points of the node N, based on the methods: N<sub>1</sub>.Descendant() and N<sub>2</sub>.Descendant(), setting proper indexes.</p>
<p>For example, we could sort the points so shared points appear at the end of the list (with the greatest indexes), and we record the index <code>overlapIndex</code> where the set of duplicated points starts.<br>
Let's call <code>Shared1</code> the set of points shared by N<sub>1</sub> and N<sub>2</sub>:</p>
<p>N<sub>1</sub>: | ................ | ..... <code>Shared1</code> ..... |</p>
<p>N<sub>2</sub>: | ................ | ..... <code>Shared1</code> ..... |</p>
<p>So, if we want to access to <code>N.Descendant(i)</code>, we will do:</p>
<pre><code>size_t Descendant(const size_t index) const
{
if (IsLeaf())
return (*pointsIndex)[index];
size_t num = left->overlapIndex;
if (index < num)
return left->Descendant(index);
if (right)
return right->Descendant(index - num);
}
</code></pre>
<p>The problem is that this can not be maintained recursively.<br>
Suppose we split N<sub>1</sub> according to another splitting hyperplane, resulting in: N<sub>11</sub> and N<sub>12</sub>.<br>
Let's call <code>Shared2</code> the set of points shared by N<sub>11</sub> and N<sub>12</sub>:</p>
<p>N<sub>11</sub>: | ................ | ..... <code>Shared2</code> ..... | ..... A subset of <code>Shared1</code>: S<sub>1</sub>..... |</p>
<p>N<sub>12</sub>: | ................ | ..... <code>Shared2</code> ..... | ..... A subset of <code>Shared1</code>: S<sub>2</sub>..... |</p>
<p>Which value do we record as <code>overlapIndex</code>? the index where S<sub>1</sub> starts or the index where <code>Shared2</code> starts?</p>
<p>If we consider the index where S<sub>1</sub> starts. We will manage to properly access the descendants points of the node N. But, we won't be able to access to all the descendants points of the node N<sub>1</sub>, because points in S<sub>1</sub> won't be considered.</p>
<p>If we consider the index where <code>Shared2</code> starts, we will manage to properly access the descendants points of the node N. But, we won't be able to access to all the descendants points of the node N<sub>1</sub>, because points in S<sub>1</sub> won't be considered.</p>
<p>So, I don't think this can be easily implemented.</p>
<p>I can think of 2 alternative solutions:</p>
<ul>
<li>Don't change anything, and add a note that <code>NumDescendants()</code> includes duplicated points. Also we should mencion that Spill Tree shouldn't be considered for <code>RangeSearch</code>.</li>
<li>Hold a list of indexes in each node, including non-leaf nodes. This would require O(n logn) space, comparing to current implementation which requires O(n) space.</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/747/files/a71b57caa90311f5542180bc0553449c3691395d#r74244401">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFFpD76JsDAfz6OReqEnPfdXRvMMMks5qedN_gaJpZM4JZzLU">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFKuA1Qx-W0rie0A8TwvTEzihai5aks5qedN_gaJpZM4JZzLU.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#r74244401"></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":"@MarcosPividori in #747: Hi,\r\nI think this is a complicated problem. I have been thinking about it for a while.\r\nThe problem is this:\r\nSuppose we have a overlapping node N with 2 children: N\u003csub\u003e1\u003c/sub\u003e and N\u003csub\u003e2\u003c/sub\u003e.\r\nAs N\u003csub\u003e1\u003c/sub\u003e and N\u003csub\u003e2\u003c/sub\u003e share some data points, we know that:\r\n\r\n N\u003csub\u003e1\u003c/sub\u003e.NumDescendants() + N\u003csub\u003e2\u003c/sub\u003e.NumDescendants() \u003e N.NumDescendants()\r\n\r\nWe want to avoid keeping a list of indexes for each non-leaf node. So, we want to access the:\r\n`[0, N.NumDescendants())` set of descendants points of the node N, based on the methods: N\u003csub\u003e1\u003c/sub\u003e.Descendant() and N\u003csub\u003e2\u003c/sub\u003e.Descendant(), setting proper indexes.\r\n\r\nFor example, we could sort the points so shared points appear at the end of the list (with the greatest indexes), and we record the index `overlapIndex` where the set of duplicated points starts.\r\nLet's call `Shared1` the set of points shared by N\u003csub\u003e1\u003c/sub\u003e and N\u003csub\u003e2\u003c/sub\u003e:\r\n\r\n N\u003csub\u003e1\u003c/sub\u003e: | ................ | ..... `Shared1` ..... |\r\n\r\n N\u003csub\u003e2\u003c/sub\u003e: | ................ | ..... `Shared1` ..... |\r\n\r\nSo, if we want to access to `N.Descendant(i)`, we will do:\r\n\r\n```\r\nsize_t Descendant(const size_t index) const\r\n{\r\n if (IsLeaf())\r\n return (*pointsIndex)[index];\r\n size_t num = left-\u003eoverlapIndex;\r\n if (index \u003c num)\r\n return left-\u003eDescendant(index);\r\n if (right)\r\n return right-\u003eDescendant(index - num);\r\n}\r\n```\r\n\r\nThe problem is that this can not be maintained recursively.\r\nSuppose we split N\u003csub\u003e1\u003c/sub\u003e according to another splitting hyperplane, resulting in: N\u003csub\u003e11\u003c/sub\u003e and N\u003csub\u003e12\u003c/sub\u003e.\r\nLet's call `Shared2` the set of points shared by N\u003csub\u003e11\u003c/sub\u003e and N\u003csub\u003e12\u003c/sub\u003e:\r\n\r\n N\u003csub\u003e11\u003c/sub\u003e: | ................ | ..... `Shared2` ..... | ..... A subset of `Shared1`: S\u003csub\u003e1\u003c/sub\u003e..... |\r\n\r\n N\u003csub\u003e12\u003c/sub\u003e: | ................ | ..... `Shared2` ..... | ..... A subset of `Shared1`: S\u003csub\u003e2\u003c/sub\u003e..... |\r\n\r\nWhich value do we record as `overlapIndex`? the index where S\u003csub\u003e1\u003c/sub\u003e starts or the index where `Shared2` starts?\r\n\r\nIf we consider the index where S\u003csub\u003e1\u003c/sub\u003e starts. We will manage to properly access the descendants points of the node N. But, we won't be able to access to all the descendants points of the node N\u003csub\u003e1\u003c/sub\u003e, because points in S\u003csub\u003e1\u003c/sub\u003e won't be considered.\r\n\r\nIf we consider the index where `Shared2` starts, we will manage to properly access the descendants points of the node N. But, we won't be able to access to all the descendants points of the node N\u003csub\u003e1\u003c/sub\u003e, because points in S\u003csub\u003e1\u003c/sub\u003e won't be considered.\r\n\r\nSo, I don't think this can be easily implemented.\r\n\r\nI can think of 2 alternative solutions:\r\n+ Don't change anything, and add a note that `NumDescendants()` includes duplicated points. Also we should mencion that Spill Tree shouldn't be considered for `RangeSearch`.\r\n+ Hold a list of indexes in each node, including non-leaf nodes. This would require O(n logn) space, comparing to current implementation which requires O(n) space."}],"action":{"name":"View Pull Request","url":"https://github.com/mlpack/mlpack/pull/747/files/a71b57caa90311f5542180bc0553449c3691395d#r74244401"}}}</script>