[mlpack-git] master: Avoid calculating the score of both child nodes when not necessary, with the Single Tree Traverser for Spill Trees. (fdc8e9c)

[gitdub at mlpack.org]

Repository : https://github.com/mlpack/mlpack
On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/0f4b25acd6aaa14294c044874ba6cc0751712baa...0a19d07bd39e6223991976474bc79671ba8aa0f0

>---------------------------------------------------------------

commit fdc8e9cd19666680e772ac89da0cd3bf1a78e1a8
Author: MarcosPividori <marcos.pividori at gmail.com>
Date:   Mon Aug 8 16:37:42 2016 -0300

    Avoid calculating the score of both child nodes when not necessary, with the Single Tree Traverser for Spill Trees.


>---------------------------------------------------------------

fdc8e9cd19666680e772ac89da0cd3bf1a78e1a8
 .../tree/spill_tree/single_tree_traverser_impl.hpp | 92 ++++++++++++++--------
 1 file changed, 60 insertions(+), 32 deletions(-)

diff --git a/src/mlpack/core/tree/spill_tree/single_tree_traverser_impl.hpp b/src/mlpack/core/tree/spill_tree/single_tree_traverser_impl.hpp
index 8cbfb8f..8d50b36 100644
--- a/src/mlpack/core/tree/spill_tree/single_tree_traverser_impl.hpp
+++ b/src/mlpack/core/tree/spill_tree/single_tree_traverser_impl.hpp
@@ -50,45 +50,39 @@ SingleTreeTraverser<RuleType>::Traverse(
   }
   else
   {
-    // If either score is DBL_MAX, we do not recurse into that node.
-    double leftScore = rule.Score(queryIndex, *referenceNode.Left());
-    double rightScore = rule.Score(queryIndex, *referenceNode.Right());
-
-    if (leftScore < rightScore)
+    if(referenceNode.Overlap())
     {
-      // Recurse to the left.
-      Traverse(queryIndex, *referenceNode.Left());
-
-      // Is it still valid to recurse to the right?
-      rightScore = rule.Rescore(queryIndex, *referenceNode.Right(), rightScore);
+      // If referenceNode is a overlapping node we do defeatist search. In this
+      // case, it is enough to calculate the score of only one child node. As we
+      // know that the query point can't be at both sides of the splitting
+      // hyperplane, the possible scores for the references child nodes are:
+      // 0 or DBL_MAX.
+      double leftScore = rule.Score(queryIndex, *referenceNode.Left());
 
-      if (rightScore != DBL_MAX)
-        Traverse(queryIndex, *referenceNode.Right()); // Recurse to the right.
-      else
+      if (leftScore == 0)
+      {
+        // Recurse to the left.
+        Traverse(queryIndex, *referenceNode.Left());
+        // Prune the right node.
         ++numPrunes;
-    }
-    else if (rightScore < leftScore)
-    {
-      // Recurse to the right.
-      Traverse(queryIndex, *referenceNode.Right());
-
-      // Is it still valid to recurse to the left?
-      leftScore = rule.Rescore(queryIndex, *referenceNode.Left(), leftScore);
-
-      if (leftScore != DBL_MAX)
-        Traverse(queryIndex, *referenceNode.Left()); // Recurse to the left.
+      }
       else
+      {
+        // Recurse to the right.
+        Traverse(queryIndex, *referenceNode.Right());
+        // Prune the left node.
         ++numPrunes;
+      }
     }
-    else // leftScore is equal to rightScore.
+    else
     {
-      if (leftScore == DBL_MAX)
-      {
-        numPrunes += 2; // Pruned both left and right.
-      }
-      else
+      // If either score is DBL_MAX, we do not recurse into that node.
+      double leftScore = rule.Score(queryIndex, *referenceNode.Left());
+      double rightScore = rule.Score(queryIndex, *referenceNode.Right());
+
+      if (leftScore < rightScore)
       {
-        // Choose the left first.
+        // Recurse to the left.
         Traverse(queryIndex, *referenceNode.Left());
 
         // Is it still valid to recurse to the right?
@@ -96,10 +90,44 @@ SingleTreeTraverser<RuleType>::Traverse(
             rightScore);
 
         if (rightScore != DBL_MAX)
-          Traverse(queryIndex, *referenceNode.Right());
+          Traverse(queryIndex, *referenceNode.Right()); // Recurse to the right.
         else
           ++numPrunes;
       }
+      else if (rightScore < leftScore)
+      {
+        // Recurse to the right.
+        Traverse(queryIndex, *referenceNode.Right());
+
+        // Is it still valid to recurse to the left?
+        leftScore = rule.Rescore(queryIndex, *referenceNode.Left(), leftScore);
+
+        if (leftScore != DBL_MAX)
+          Traverse(queryIndex, *referenceNode.Left()); // Recurse to the left.
+        else
+          ++numPrunes;
+      }
+      else // leftScore is equal to rightScore.
+      {
+        if (leftScore == DBL_MAX)
+        {
+          numPrunes += 2; // Pruned both left and right.
+        }
+        else
+        {
+          // Choose the left first.
+          Traverse(queryIndex, *referenceNode.Left());
+
+          // Is it still valid to recurse to the right?
+          rightScore = rule.Rescore(queryIndex, *referenceNode.Right(),
+              rightScore);
+
+          if (rightScore != DBL_MAX)
+            Traverse(queryIndex, *referenceNode.Right());
+          else
+            ++numPrunes;
+        }
+      }
     }
   }
 }