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

MarcosPividori notifications at github.com
Thu Aug 11 11:58:45 EDT 2016

Hi @rcurtin,

Thanks for your comments.

We can do *"pure defeatist search"* with `SpillTrees`, without implementing a new tree traversal `DefeatistTreeTraversel`.

If we set: `rho = 0.99999`, all nodes will be *overlapping nodes*, and the spill tree's traversers will do defeatist search when visiting each of them.

The problem with that approach, which *hybrid spill tree* aims to solve, is that the tree can be really big. We can't be sure that the tree is reduced by a constant factor.

The default value for *rho* is: `0.7`. If we consider higher values, we will spend more time building the tree, but less time searching for the neighbors. The opposite for lower values of *rho*.

So, I think it only make sense to create a new `DefeatistTreeTraverser` if we want to do defeatist search with other tree types, different to `SpillTrees`. Would you agree?

In that case I don't think we need to implement a new method: `GetNearestChild()` for each Tree Type. We could continue considering the `Score()` method, evaluating each child and choosing the one with lowest score. (We could modify the `DefeatistTreeTraverser` class for `SpillTrees` to avoid calculating the projections of both nodes, calculate the score of one child, and decide based on that score without calculating the score of the second child, as I mentioned before).
The only problem is that Score() would include the unnecessary overhead of CalculateBounds() which will be ignored by *pure defeatist search*. We should think how to avoid that.

What do you think? If you agree I can work on this once we finish with this PR.


You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160811/4ed63a2d/attachment.html>

More information about the mlpack-git mailing list