[mlpack-svn] [MLPACK] #156: Further generalization of trees to include cover trees

MLPACK Trac trac at coffeetalk-1.cc.gatech.edu
Sat Aug 4 23:07:43 EDT 2012


#156: Further generalization of trees to include cover trees
----------------------------------------------------------+-----------------
  Reporter:  rcurtin                                      |        Owner:              
      Type:  wishlist                                     |       Status:  closed      
  Priority:  major                                        |    Milestone:  mlpack 1.0.2
 Component:  mlpack                                       |   Resolution:  fixed       
  Keywords:  tree cover kd-tree generalization templates  |     Blocking:              
Blocked By:                                               |  
----------------------------------------------------------+-----------------
Changes (by rcurtin):

  * status:  new => closed
  * resolution:  => fixed


Comment:

 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.

-- 
Ticket URL: <http://trac.research.cc.gatech.edu/fastlab/ticket/156#comment:3>
MLPACK <www.fast-lab.org>
MLPACK is an intuitive, fast, and scalable C++ machine learning library developed by the FASTLAB at Georgia Tech under Dr. Alex Gray.


More information about the mlpack-svn mailing list