[mlpack-git] master, mlpack-1.0.x: Fix regression in r16308, which slowed down cover tree traversals by potentially up to 50% (at least, that's the slowdown I saw...). (bb171e3)

[gitdub at big.cc.gt.atl.ga.us]

Repository : https://github.com/mlpack/mlpack

On branches: master,mlpack-1.0.x
Link       : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40

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

commit bb171e3ee2a3e779035e37d8427704164ef98d99
Author: Ryan Curtin <ryan at ratml.org>
Date:   Mon Mar 3 13:47:31 2014 +0000

    Fix regression in r16308, which slowed down cover tree traversals by potentially
    up to 50% (at least, that's the slowdown I saw...).


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

bb171e3ee2a3e779035e37d8427704164ef98d99
 .../neighbor_search/neighbor_search_rules_impl.hpp | 36 ++++++++++++++++------
 1 file changed, 26 insertions(+), 10 deletions(-)

diff --git a/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp b/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp
index 4611799..f7e1040 100644
--- a/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp
@@ -181,13 +181,21 @@ inline double NeighborSearchRules<SortPolicy, MetricType, TreeType>::Score(
     const double queryAdjust = queryParentDist + queryDescDist;
     adjustedScore = SortPolicy::CombineBest(adjustedScore, queryAdjust);
   }
+  else if (traversalInfo.LastQueryNode() == &queryNode)
+  {
+    adjustedScore = SortPolicy::CombineBest(adjustedScore, queryDescDist);
+  }
   else
   {
-    // If the parent node is NULL, force adjustedScore to be such that it can't
-    // be pruned.  Otherwise use the parent descendant distance.
-    const double queryParentDescDist = (queryNode.Parent() == NULL) ?
-        bestDistance : queryNode.Parent()->FurthestDescendantDistance();
-    adjustedScore = SortPolicy::CombineBest(adjustedScore, queryParentDescDist);
+    // The last query node wasn't this query node or its parent.  So we force
+    // the adjustedScore to be such that this combination can't be pruned here,
+    // because we don't really know anything about it.
+
+    // It would be possible to modify this section to try and make a prune based
+    // on the query descendant distance and the distance between the query node
+    // and last traversal query node, but this case doesn't actually happen for
+    // kd-trees or cover trees.
+    adjustedScore = SortPolicy::CombineBest(adjustedScore, bestDistance);
   }
 
   if (traversalInfo.LastReferenceNode() == referenceNode.Parent())
@@ -195,13 +203,21 @@ inline double NeighborSearchRules<SortPolicy, MetricType, TreeType>::Score(
     const double refAdjust = refParentDist + refDescDist;
     adjustedScore = SortPolicy::CombineBest(adjustedScore, refAdjust);
   }
+  else if (traversalInfo.LastReferenceNode() == &referenceNode)
+  {
+    adjustedScore = SortPolicy::CombineBest(adjustedScore, refDescDist);
+  }
   else
   {
-    // If the parent node is NULL, force adjustedScore to be such that it can't
-    // be pruned.  Otherwise use the parent descendant distance.
-    const double refParentDescDist = (referenceNode.Parent() == NULL) ?
-        bestDistance : referenceNode.Parent()->FurthestDescendantDistance();
-    adjustedScore = SortPolicy::CombineBest(adjustedScore, refParentDescDist);
+    // The last reference node wasn't this reference node or its parent.  So we
+    // force the adjustedScore to be such that this combination can't be pruned
+    // here, because we don't really know anything about it.
+
+    // It would be possible to modify this section to try and make a prune based
+    // on the reference descendant distance and the distance between the
+    // reference node and last traversal reference node, but this case doesn't
+    // actually happen for kd-trees or cover trees.
+    adjustedScore = SortPolicy::CombineBest(adjustedScore, bestDistance);
   }
 
   // Can we prune?