[mlpack-svn] [MLPACK] #367: Ball trees are not guaranteed to have decreasing child furthest descendant distances

[MLPACK Trac]

#367: Ball trees are not guaranteed to have decreasing child furthest descendant
distances
---------------------+------------------------------------------------------
 Reporter:  rcurtin  |        Owner:                                                                  
     Type:  defect   |       Status:  new                                                             
 Priority:  minor    |    Milestone:  mlpack 1.1.0                                                    
Component:  mlpack   |     Keywords:  ballbound, ball tree, allknn, furthest descendant distance, tree
 Blocking:           |   Blocked By:                                                                  
---------------------+------------------------------------------------------
 The BallBound class uses an iterative algorithm to determine a bounding
 ball of a set of points.  But this is not guaranteed to be the minimum
 bounding ball.  This means that a parent node may end up with a bounding
 ball that has radius smaller than the bounding balls of its children!
 This may break the assumption that the FurthestDescendantDistance() of a
 child is smaller than the FurthestDescendantDistance() of the parent.

 In r17121 I have committed a workaround fix, which makes NeighborSearch
 work correctly with ball trees, but that workaround (the use of
 std::min()) should be removed when this bug is resolved.

 For this bug to be resolved, we must be able to guarantee that any
 `BinarySpaceTree<BallBound<...>, ...>` tree is such that the parent node's
 furthest descendant distance is _always_ larger than any child's furthest
 descendant distance.  This probably requires a rewrite and rethink of the
 algorithm implemented in `BallBound<>::operator|=(MatType&)`.

-- 
Ticket URL: <http://trac.research.cc.gatech.edu/fastlab/ticket/367>
MLPACK <www.fast-lab.org>
MLPACK is an intuitive, fast, and scalable C++ machine learning library developed at Georgia Tech.