Further generalization of trees to include cover trees #157

Closed
rcurtin opened this Issue Dec 29, 2014 · 2 comments

Projects

None yet

1 participant

@rcurtin
Member
rcurtin commented Dec 29, 2014

Reported by rcurtin on 26 Sep 41833825 05:35 UTC
There is an implementation of cover trees in Bill's contrib/ code that should be taken and added to core/tree/. We need to figure out how to make our own tree usage more generalized so that a user can either pass a BinarySpaceTree or a CoverTree to a method.

@rcurtin rcurtin self-assigned this Dec 29, 2014
@rcurtin rcurtin added this to the mlpack 1.0.2 milestone Dec 29, 2014
@rcurtin rcurtin closed this Dec 29, 2014
@rcurtin
Member
rcurtin commented Dec 29, 2014

Commented by rcurtin on 19 Dec 42324071 12:04 UTC
I took Pari's implementation (which was very similar to Bill's) and used it to write a new implementation which is in src/mlpack/core/tree/cover_tree.hpp and src/mlpack/core/tree/cover_tree_impl.hpp in r12552 (tests in r12553). Because this tree type can have multiple children, any classes that use a BinarySearchTree have to be adapted in some way. Where before this was written:

Recurse(tree.Left());
Recurse(tree.Right());

we really should now use something more like

for (size_t i = 0; i < tree.NumChildren(); ++i)
  Recurse(tree.Child(i));
@rcurtin
Member
rcurtin commented Dec 29, 2014

Commented by rcurtin on 26 Mar 42595946 14:51 UTC
After some serious thought I have restructured the core/tree directory so that BinarySpaceTree and CoverTree have their own directories. In addition, each of these classes has a SingleTreeTraverser and a DualTreeTraverser so that a dual-tree method can be written without having to consider the right way to traverse the tree. This change was made in NeighborSearch in r13333.

Each tree-traversing method should define a RuleType class which implements the actual search in a callback-like function. The tree traverser may call any of the following methods during the search:

  • bool CanPrune(q, r)
  • void BaseCase(q, r)
  • bool LeftFirst(q, r) -- specific to BinarySpaceTree
  • void RecursionOrder(q, r, order) -- not yet implemented, for now is probably specific to CoverTree

Once those methods are implemented one should be able to create a TreeType::DualTreeTraverser<RuleType> object and perform the traversal like that. Therefore, I think the generalization of MLPACK trees to cover trees is complete and ready to generalize further to other types of trees.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment