# [mlpack-git] [mlpack/mlpack] Spill trees (#747)

Wed Aug 10 11:52:10 EDT 2016

```> +  }
> +
> +  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();

Yes, I have thought of that approach that you mention, and many similar options. I tried to explain the problem in the previous post, but it is a bit difficult to formulate.
Suppose I implement your approach. And we have a tree of 2 levels of overlapping nodes:
```
N
|''''''''''\
N_1          N_2
|  \         |   \
N_11  N_12   N_21  N_22
```
The problem is how to organize the points in the second level, in the nodes `N_21` and nodes `N_22`.
Suppose we want to get the `i-th` descendant point of the node N, included in N_2, but not included in N_1.
This means when `i >= N_1.NumDescendants()`.

Let U: points held in both N_1 and N_2.

As,  N_2 is splitted in N_21 and N_22 by another different hyperplane, some points of U will be included in N_21 and some points of U will be included in N_22.

If `i < N_1.NumDescendants() + N_21.NumDescendants()`, we will call: `N_21.Descendant( i - N_1.NumDescendants())`

As N_21 includes some points from U, we can repeat a point that was included in the node N_1.

---
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/mlpack/mlpack/pull/747/files/a71b57caa90311f5542180bc0553449c3691395d#r74272371
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160810/4b71c8d3/attachment.html>
```