[mlpack-git] master: Elkan pruning can't prune the best query node. Bugfix. Trivial slowdown. (f8a73a3)

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

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

On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/eddd7167d69b6c88b271ef2e51d1c20e13f1acd8...70342dd8e5c17e0c164cfb8189748671e9c0dd44

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

commit f8a73a38ae2e3eb91e6c7b513bb5e6d12acd9d38
Author: Ryan Curtin <ryan at ratml.org>
Date:   Wed Jan 14 16:50:34 2015 -0500

    Elkan pruning can't prune the best query node. Bugfix. Trivial slowdown.


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

f8a73a38ae2e3eb91e6c7b513bb5e6d12acd9d38
 src/mlpack/methods/kmeans/dual_tree_kmeans_rules_impl.hpp | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/src/mlpack/methods/kmeans/dual_tree_kmeans_rules_impl.hpp b/src/mlpack/methods/kmeans/dual_tree_kmeans_rules_impl.hpp
index d456c83..321de5d 100644
--- a/src/mlpack/methods/kmeans/dual_tree_kmeans_rules_impl.hpp
+++ b/src/mlpack/methods/kmeans/dual_tree_kmeans_rules_impl.hpp
@@ -112,8 +112,6 @@ double DualTreeKMeansRules<MetricType, TreeType>::Score(
 
   traversalInfo.LastReferenceNode() = &referenceNode;
 
-  double score = ElkanTypeScore(queryNode, referenceNode);
-
   // If there's no closest query node assigned, but the parent has one, take
   // that one.
   if (referenceNode.Stat().ClosestQueryNode() == NULL &&
@@ -127,6 +125,8 @@ double DualTreeKMeansRules<MetricType, TreeType>::Score(
         referenceNode.Stat().MaxQueryNodeDistance());
   }
 
+  double score = ElkanTypeScore(queryNode, referenceNode);
+
   if (score != DBL_MAX)
   {
     // We also have to update things if the closest query node is null.  This
@@ -229,16 +229,20 @@ double DualTreeKMeansRules<MetricType, TreeType>::ElkanTypeScore(
 
 template<typename MetricType, typename TreeType>
 double DualTreeKMeansRules<MetricType, TreeType>::ElkanTypeScore(
-    TreeType& /* queryNode */,
+    TreeType& queryNode,
     TreeType& referenceNode,
     const double minQueryDistance) const
 {
   // See if we can do an Elkan-type prune on between-centroid distances.
+
   const double maxDistance = referenceNode.Stat().MaxQueryNodeDistance();
   if (maxDistance == DBL_MAX)
     return minQueryDistance;
 
-  if (minQueryDistance > 2.0 * maxDistance)
+  if ((minQueryDistance > 2.0 * maxDistance) &&
+      !(IsDescendantOf(*(TreeType*) referenceNode.Stat().ClosestQueryNode(),
+          queryNode)) &&
+      (&queryNode != (TreeType*) referenceNode.Stat().ClosestQueryNode()))
   {
     // Then we can conclude d_max(best(N_r), N_r) <= d_min(N_q, N_r) which
     // means that N_q cannot possibly hold any clusters that own any points in