[mlpack-svn] r14095 - mlpack/trunk/src/mlpack/methods/neighbor_search

[fastlab-svn at coffeetalk-1.cc.gatech.edu]

Author: rcurtin
Date: 2013-01-09 15:44:07 -0500 (Wed, 09 Jan 2013)
New Revision: 14095

Modified:
   mlpack/trunk/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp
Log:
Better calculation of bound.  We could still optimize a little bit.  Debug
output is for #243; this solves #264.


Modified: mlpack/trunk/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp	2013-01-09 19:48:26 UTC (rev 14094)
+++ mlpack/trunk/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp	2013-01-09 20:44:07 UTC (rev 14095)
@@ -226,16 +226,47 @@
       childBound = bound;
   }
 
+  // If there are no points, then break; the bound must be the child bound.
+  if (queryNode.NumPoints() == 0)
+    return childBound;
+
+  // If there are no children, then break; the bound must be the point bound.
+  if (queryNode.NumChildren() == 0)
+    return pointBound;
+
+//  Log::Debug << "Point bound " << pointBound << std::endl;
+//  Log::Debug << "Child bound " << childBound << std::endl;
+//  Log::Debug << "Furthest descendant distance " << maxDescendantDistance <<
+//      std::endl;
+
   // If the bound of the children is uninitialized
   // (SortPolicy::WorstDistance()), then maybe we can create a bound for the
   // children.  But this requires a point bound to exist.
-  if (childBound == SortPolicy::WorstDistance() &&
-      pointBound != SortPolicy::BestDistance()) // This could fail!
-      // SortPolicy::BestDistance() could be a valid bound!
+
+  // It is possible that we could calculate a better bound for the children.
+  if (pointBound != SortPolicy::WorstDistance())
   {
-    // Should we be considering queryNode.Stat().Bound() too?
-    childBound = pointBound + maxDescendantDistance;
-    Log::Debug << "Child bound is " << childBound << std::endl;
+    const double pointChildBound = pointBound + maxDescendantDistance;
+//    Log::Debug << "Point-child bound is " << pointChildBound << std::endl;
+
+    if (SortPolicy::IsBetter(pointChildBound, childBound))
+    {
+      // The calculated bound is a tighter bound than the existing child bounds.
+      // Update all of the child bounds to this new, tighter bound.
+      for (size_t i = 0; i < queryNode.NumChildren(); ++i)
+      {
+//        Log::Debug << "Update child " << i << " bound from " <<
+//            queryNode.Child(i).Stat().Bound() << " to " << pointChildBound <<
+//            std::endl;
+        if (SortPolicy::IsBetter(pointChildBound,
+            queryNode.Child(i).Stat().Bound()))
+          queryNode.Child(i).Stat().Bound() = pointChildBound;
+//        else
+//          Log::Debug << "Did not update child!\n";
+      }
+
+      childBound = pointChildBound;
+    }
   }
 
   // Return the worse of the two bounds.