[mlpack-git] master: Explicitly relax the separation invariant (it was already relaxed in the code). (3f5503b)

[gitdub at mlpack.org]

Repository : https://github.com/mlpack/mlpack
On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/02e7f5decaee4fba970f3b7a952b8eda1c5b43dc...3f5503bfe71dbbda4b4551c9cdfaba8b819565ad

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

commit 3f5503bfe71dbbda4b4551c9cdfaba8b819565ad
Author: Ryan Curtin <ryan at ratml.org>
Date:   Thu Sep 15 11:24:23 2016 -0400

    Explicitly relax the separation invariant (it was already relaxed in the code).


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

3f5503bfe71dbbda4b4551c9cdfaba8b819565ad
 src/mlpack/core/tree/cover_tree/cover_tree.hpp |  8 +--
 src/mlpack/tests/tree_test.cpp                 | 72 +++-----------------------
 2 files changed, 13 insertions(+), 67 deletions(-)

diff --git a/src/mlpack/core/tree/cover_tree/cover_tree.hpp b/src/mlpack/core/tree/cover_tree/cover_tree.hpp
index 38a9f98..15316bf 100644
--- a/src/mlpack/core/tree/cover_tree/cover_tree.hpp
+++ b/src/mlpack/core/tree/cover_tree/cover_tree.hpp
@@ -23,14 +23,16 @@ namespace tree {
  *
  * The tree can be thought of as a hierarchy with the root node at the top level
  * and the leaf nodes at the bottom level.  Each level in the tree has an
- * assigned 'scale' i.  The tree follows these three conditions:
+ * assigned 'scale' i.  The tree follows these two invariants:
  *
  * - nesting: the level C_i is a subset of the level C_{i - 1}.
  * - covering: all node in level C_{i - 1} have at least one node in the
  *     level C_i with distance less than or equal to b^i (exactly one of these
  *     is a parent of the point in level C_{i - 1}.
- * - separation: all nodes in level C_i have distance greater than b^i to all
- *     other nodes in level C_i.
+ *
+ * Note that in the cover tree paper, there is a third invariant (the
+ * 'separation invariant'), but that does not apply to our implementation,
+ * because we have relaxed the invariant.
  *
  * The value 'b' refers to the base, which is a parameter of the tree.  These
  * three properties make the cover tree very good for fast, high-dimensional
diff --git a/src/mlpack/tests/tree_test.cpp b/src/mlpack/tests/tree_test.cpp
index 507a3e9..d4bbb9e 100644
--- a/src/mlpack/tests/tree_test.cpp
+++ b/src/mlpack/tests/tree_test.cpp
@@ -1833,62 +1833,6 @@ void CheckCovering(const TreeType& node)
   }
 }
 
-template<typename TreeType, typename MetricType>
-void CheckIndividualSeparation(const TreeType& constantNode,
-                               const TreeType& node)
-{
-  // Don't check points at a lower scale.
-  if (node.Scale() < constantNode.Scale())
-    return;
-
-  // If at a higher scale, recurse.
-  if (node.Scale() > constantNode.Scale())
-  {
-    for (size_t i = 0; i < node.NumChildren(); ++i)
-    {
-      // Don't recurse into leaves.
-      if (node.Child(i).NumChildren() > 0)
-        CheckIndividualSeparation<TreeType, MetricType>(constantNode,
-            node.Child(i));
-    }
-
-    return;
-  }
-
-  // Don't compare the same point against itself.
-  if (node.Point() == constantNode.Point())
-    return;
-
-  // Now we know we are at the same scale, so make the comparison.
-  const typename TreeType::Mat& dataset = constantNode.Dataset();
-  const size_t constantPoint = constantNode.Point();
-  const size_t nodePoint = node.Point();
-
-  // Make sure the distance is at least the following value (in accordance with
-  // the separation principle of cover trees).
-  double minDistance = pow(constantNode.Base(),
-      constantNode.Scale());
-
-  double distance = MetricType::Evaluate(dataset.col(constantPoint),
-      dataset.col(nodePoint));
-
-  BOOST_REQUIRE_GE(distance, minDistance);
-}
-
-template<typename TreeType, typename MetricType>
-void CheckSeparation(const TreeType& node, const TreeType& root)
-{
-  // Check the separation between this point and all other points on this scale.
-  CheckIndividualSeparation<TreeType, MetricType>(node, root);
-
-  // Check the children, but only if they are not leaves.  Leaves don't need to
-  // be checked.
-  for (size_t i = 0; i < node.NumChildren(); ++i)
-    if (node.Child(i).NumChildren() > 0)
-      CheckSeparation<TreeType, MetricType>(node.Child(i), root);
-}
-
-
 /**
  * Create a simple cover tree and then make sure it is valid.
  */
@@ -1942,8 +1886,8 @@ BOOST_AUTO_TEST_CASE(SimpleCoverTreeConstructionTest)
   // than or equal to a certain distance apart).
   CheckCovering<TreeType, LMetric<2, true>>(tree);
 
-  // Each node's children must be separated by at least a certain value.
-  CheckSeparation<TreeType, LMetric<2, true>>(tree, tree);
+  // There's no need to check the separation invariant because that is relaxed
+  // in our implementation.
 }
 
 /**
@@ -1974,8 +1918,8 @@ BOOST_AUTO_TEST_CASE(CoverTreeConstructionTest)
   // than or equal to a certain distance apart).
   CheckCovering<TreeType, LMetric<2, true> >(tree);
 
-  // Each node's children must be separated by at least a certain value.
-  CheckSeparation<TreeType, LMetric<2, true> >(tree, tree);
+  // There's no need to check the separation because that is relaxed in our
+  // implementation.
 }
 
 /**
@@ -2006,8 +1950,8 @@ BOOST_AUTO_TEST_CASE(SparseCoverTreeConstructionTest)
   // than or equal to a certain distance apart).
   CheckCovering<TreeType, LMetric<2, true> >(tree);
 
-  // Each node's children must be separated by at least a certain value.
-  CheckSeparation<TreeType, LMetric<2, true> >(tree, tree);
+  // There's no need to check the separation invariant because that is relaxed
+  // in our implementation.
 }
 
 /**
@@ -2059,8 +2003,8 @@ BOOST_AUTO_TEST_CASE(CoverTreeAlternateMetricTest)
   // than or equal to a certain distance apart).
   CheckCovering<TreeType, ManhattanDistance>(tree);
 
-  // Each node's children must be separated by at least a certain value.
-  CheckSeparation<TreeType, ManhattanDistance>(tree, tree);
+  // There's no need to check the separation invariant because that is relaxed
+  // in our implementation.
 }
 
 /**