[mlpack-svn] r13959 - in mlpack/trunk/src/mlpack/core/tree: binary_space_tree cover_tree

fastlab-svn at coffeetalk-1.cc.gatech.edu fastlab-svn at coffeetalk-1.cc.gatech.edu
Thu Nov 29 19:12:53 EST 2012


Author: rcurtin
Date: 2012-11-29 19:12:53 -0500 (Thu, 29 Nov 2012)
New Revision: 13959

Modified:
   mlpack/trunk/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser_impl.hpp
   mlpack/trunk/src/mlpack/core/tree/cover_tree/dual_tree_traverser_impl.hpp
Log:
Don't use UpdateAfterRecursion().


Modified: mlpack/trunk/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser_impl.hpp	2012-11-30 00:12:45 UTC (rev 13958)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser_impl.hpp	2012-11-30 00:12:53 UTC (rev 13959)
@@ -231,9 +231,6 @@
       }
     }
   }
-
-  // Now update any necessary information after recursion.
-  rule.UpdateAfterRecursion(queryNode, referenceNode);
 }
 
 }; // namespace tree

Modified: mlpack/trunk/src/mlpack/core/tree/cover_tree/dual_tree_traverser_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/cover_tree/dual_tree_traverser_impl.hpp	2012-11-30 00:12:45 UTC (rev 13958)
+++ mlpack/trunk/src/mlpack/core/tree/cover_tree/dual_tree_traverser_impl.hpp	2012-11-30 00:12:53 UTC (rev 13959)
@@ -64,7 +64,7 @@
   rootRefEntry.queryIndex = queryNode.Point();
   rootRefEntry.baseCase = rule.BaseCase(queryNode.Point(),
       referenceNode.Point());
-  rule.UpdateAfterRecursion(queryNode, referenceNode);
+//  rule.UpdateAfterRecursion(queryNode, referenceNode);
 
   refMap[referenceNode.Scale()].push_back(rootRefEntry);
 
@@ -97,7 +97,9 @@
   if ((queryNode.Scale() != INT_MIN) &&
       (queryNode.Scale() >= (*referenceMap.rbegin()).first))
   {
-    // Recurse into the non-self-children first.
+    // Recurse into the non-self-children first.  The recursion order cannot
+    // affect the runtime of the algorithm, because each query child recursion's
+    // results are separate and independent.
     for (size_t i = 1; i < queryNode.NumChildren(); ++i)
     {
       std::map<int, std::vector<MapEntryType> > childMap;
@@ -167,10 +169,6 @@
 //    Log::Debug << "Not pruned, performing base case " << queryNode.Point() <<
 //        " " << pointVector[i].referenceNode->Point() << "\n";
     rule.BaseCase(queryNode.Point(), pointVector[i].referenceNode->Point());
-    rule.UpdateAfterRecursion(queryNode, *pointVector[i].referenceNode);
-//    Log::Debug << "Bound for point " << queryNode.Point() << " scale " <<
-//        queryNode.Scale() << " is now " << queryNode.Stat().Bound() <<
-//        std::endl;
   }
 }
 
@@ -185,8 +183,8 @@
         RootPointPolicy, StatisticType> > >& childMap)
 {
 //  Log::Debug << "Prep for recurse into query child point " <<
-//      queryNode.Child(i).Point() << " scale " << queryNode.Child(i).Scale()
-//      << std::endl;
+//      candidateQueryNode.Point() << " scale " <<
+//      candidateQueryNode.Scale() << std::endl;
   typedef DualCoverTreeMapEntry<MetricType, RootPointPolicy, StatisticType>
       MapEntryType;
 
@@ -228,11 +226,11 @@
       }
 
       // Evaluate base case.
-//      Log::Debug << "Must evaluate base case " << queryNode.Child(i).Point()
-//         << " " << refNode->Point() << "\n";
+//      Log::Debug << "Must evaluate base case "
+//          << candidateQueryNode.Point() << " " << refNode->Point()
+//          << "\n";
       double baseCase = rule.BaseCase(candidateQueryNode.Point(),
           refNode->Point());
-      rule.UpdateAfterRecursion(candidateQueryNode, *refNode);
 //      Log::Debug << "Base case was " << baseCase << std::endl;
 
       score = rule.Score(candidateQueryNode, *refNode, baseCase);
@@ -271,8 +269,8 @@
         StatisticType> > >& referenceMap)
 {
 //  Log::Debug << "Prep for recurse into query self-child point " <<
-//      queryNode.Child(0).Point() << " scale " << queryNode.Child(0).Scale()
-//      << std::endl;
+//      candidateQueryNode.Point() << " scale " <<
+//      candidateQueryNode.Scale() << std::endl;
   typedef DualCoverTreeMapEntry<MetricType, RootPointPolicy, StatisticType>
       MapEntryType;
 
@@ -281,7 +279,7 @@
   // in this setting we do not recurse into any children of the reference
   // entries.
   typename std::map<int, std::vector<MapEntryType> >::reverse_iterator it =
-    referenceMap.rbegin();
+      referenceMap.rbegin();
 
   while (it != referenceMap.rend() && (*it).first != INT_MIN)
   {
@@ -305,9 +303,9 @@
       const size_t queryIndex = frame.queryIndex;
       const size_t refIndex = frame.referenceIndex;
 
-      //        Log::Debug << "Recheck reference node " << refNode->Point() <<
-      //            " scale " << refNode->Scale() << " which has old score " <<
-      //            oldScore << std::endl;
+//      Log::Debug << "Recheck reference node " << refNode->Point() << " scale "
+//          << refNode->Scale() << " which has old score " << oldScore
+//          << std::endl;
 
       // Have we performed the base case yet?
       double score;
@@ -325,12 +323,11 @@
 
         // If not pruned, we have to perform the base case.
         baseCase = rule.BaseCase(candidateQueryNode.Point(), refNode->Point());
-        rule.UpdateAfterRecursion(candidateQueryNode, *refNode);
       }
 
       score = rule.Score(candidateQueryNode, *refNode, baseCase);
 
-      //        Log::Debug << "Rescored as " << score << std::endl;
+//      Log::Debug << "Rescored as " << score << std::endl;
 
       if (score == DBL_MAX)
       {
@@ -339,7 +336,7 @@
         continue;
       }
 
-      //        Log::Debug << "Kept in map\n";
+//      Log::Debug << "Kept in map\n";
 
       // Add to child map.
       newScaleVector.push_back(frame);
@@ -372,6 +369,12 @@
   // the query node.
   while ((*referenceMap.rbegin()).first > queryNode.Scale())
   {
+    // If the query node's scale is INT_MIN and the reference map's maximum
+    // scale is INT_MIN, don't try to recurse...
+    if ((queryNode.Scale() == INT_MIN) &&
+       ((*referenceMap.rbegin()).first == INT_MIN))
+      break;
+
     // Get a reference to the current largest scale.
     std::vector<MapEntryType>& scaleVector = (*referenceMap.rbegin()).second;
 
@@ -402,7 +405,7 @@
       // First we recalculate the score of this node to find if we can prune it.
       if (rule.Rescore(queryNode, *refNode, score) == DBL_MAX)
       {
- //       Log::Warn << "Pruned after rescore\n";
+//        Log::Warn << "Pruned after rescore\n";
         ++numPrunes;
         continue;
       }
@@ -416,10 +419,6 @@
 //            << refPoint << "\n";
         baseCase = rule.BaseCase(queryNode.Point(), refPoint);
 //        Log::Debug << "Base case " << baseCase << std::endl;
-        rule.UpdateAfterRecursion(queryNode, *refNode); // Kludgey.
-//        Log::Debug << "Bound for point " << queryNode.Point() << " scale " <<
-//            queryNode.Scale() << " is now " << queryNode.Stat().Bound() <<
-//            std::endl;
       }
 
       // Create the score for the children.
@@ -462,7 +461,6 @@
 
         // Calculate the base case of each child.
         baseCase = rule.BaseCase(queryIndex, refIndex);
-        rule.UpdateAfterRecursion(queryNode, refNode->Child(j));
 
         // See if we can prune it.
         childScore = rule.Score(queryNode, refNode->Child(j), baseCase);




More information about the mlpack-svn mailing list