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

[MarcosPividori]

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.

Thanks!


-- 
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#issuecomment-239206014
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160811/4ed63a2d/attachment.html>