[mlpack-svn] [MLPACK] #282: create a "worst-case" tree type to test algorithms with

[MLPACK Trac]

#282: create a "worst-case" tree type to test algorithms with
----------------------+-----------------------------------------------------
 Reporter:  rcurtin   |        Owner:                                    
     Type:  wishlist  |       Status:  new                               
 Priority:  minor     |    Milestone:  mlpack 1.1.0                      
Component:  mlpack    |     Keywords:  dual-tree algorithms, tree, random
 Blocking:            |   Blocked By:                                    
----------------------+-----------------------------------------------------
 In the paper 'Tree-Independent Dual-Tree Algorithms'
 (http://arxiv.org/abs/1304.4327) the general definitions for a space tree
 are laid out.  All of the dual-tree algorithms are written in the
 generalized format detailed in the paper (or, well... they should be
 converted...).  However, I'm nearly certain that the algorithms, as
 implemented, won't work for any arbitrary space tree type.

 So, we should make some kind of space tree which is meant to test these
 algorithms (keep in mind it is not meant to perform the algorithm
 quickly).

 I think it should maybe look something like this:

  * At the creation of each node, it is given a list of points which are
 going to be its descendants.  It picks a random subset of these to be its
 own points, and then passes the rest of the points, plus maybe some of its
 own points, to its children.  This way we get points that are in one
 level, but not the next, but then also in the one after that.

  * The convex subsets represented by each node can (and maybe should) be
 overlapping.

  * The way the convex subsets are expressed should not be dimension-
 specific.  Maybe some kind of n-gon which encloses the descendant points
 and where n is some random number that is different at each node.

  * Some child nodes should be identical copies of the parent node.

 Then, if this is implemented, we will almost certainly find that our dual-
 tree algorithms, as implemented, don't always work with any type of space
 tree.

-- 
Ticket URL: <http://trac.research.cc.gatech.edu/fastlab/ticket/282>
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.