[mlpack-git] master, mlpack-1.0.x: Fix elusive bug that only occurred in particularly rare situations. (cae0701)

[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 cae07019cd98a1221e374de33940fbbcbea4372f
Author: Ryan Curtin <ryan at ratml.org>
Date:   Thu Jul 10 14:04:45 2014 +0000

    Fix elusive bug that only occurred in particularly rare situations.


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

cae07019cd98a1221e374de33940fbbcbea4372f
 .../methods/neighbor_search/neighbor_search_rules_impl.hpp | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 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 5b4eca9..5b4bb2b 100644
--- a/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp
@@ -151,7 +151,9 @@ inline double NeighborSearchRules<SortPolicy, MetricType, TreeType>::Score(
   const double score = traversalInfo.LastScore();
   double adjustedScore;
 
-  // In some cases we can just use the last base case.
+  // We want to set adjustedScore to be the distance between the centroid of the
+  // last query node and last reference node.  We will do this by adjusting the
+  // last score.  In some cases, we can just use the last base case.
   if (tree::TreeTraits<TreeType>::FirstPointIsCentroid)
   {
     adjustedScore = traversalInfo.LastBaseCase();
@@ -162,10 +164,16 @@ inline double NeighborSearchRules<SortPolicy, MetricType, TreeType>::Score(
   }
   else
   {
+    // The last score is equal to the distance between the centroids minus the
+    // radii of the query and reference bounds along the axis of the line
+    // between the two centroids.  In the best case, these radii are the
+    // furthest descendant distances, but that is not always true.  It would
+    // take too long to calculate the exact radii, so we are forced to use
+    // MinimumBoundDistance() as a lower-bound approximation.
     const double lastQueryDescDist =
-        traversalInfo.LastQueryNode()->FurthestDescendantDistance();
+        traversalInfo.LastQueryNode()->MinimumBoundDistance();
     const double lastRefDescDist =
-        traversalInfo.LastReferenceNode()->FurthestDescendantDistance();
+        traversalInfo.LastReferenceNode()->MinimumBoundDistance();
     adjustedScore = SortPolicy::CombineWorst(score, lastQueryDescDist);
     adjustedScore = SortPolicy::CombineWorst(score, lastRefDescDist);
   }