[mlpack-git] master, mlpack-1.0.x: Cache the distance from the center of the node to the center of the parent node. (551bde4)

[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 551bde4dd5b37357e3163801649a468244bae58f
Author: Ryan Curtin <ryan at ratml.org>
Date:   Thu Feb 6 19:55:32 2014 +0000

    Cache the distance from the center of the node to the center of the parent node.


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

551bde4dd5b37357e3163801649a468244bae58f
 .../tree/binary_space_tree/binary_space_tree.hpp   |  9 ++++++
 .../binary_space_tree/binary_space_tree_impl.hpp   | 36 ++++++++++++++++++++--
 2 files changed, 43 insertions(+), 2 deletions(-)

diff --git a/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp b/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
index 76ee972..1fcaa0c 100644
--- a/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
+++ b/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
@@ -57,6 +57,8 @@ class BinarySpaceTree
   StatisticType stat;
   //! The dimension this node split on if it is a parent.
   size_t splitDimension;
+  //! The distance from the centroid of this node to the centroid of the parent.
+  double parentDistance;
   //! The distance to the furthest descendant, cached to speed things up.
   double furthestDescendantDistance;
   //! The dataset.
@@ -299,6 +301,13 @@ class BinarySpaceTree
    */
   double FurthestDescendantDistance() const;
 
+  //! Modify the distance from the center of this node to the center of the
+  //! parent node.
+  double& ParentDistance() { return parentDistance; }
+  //! Return the distance from the center of this node to the center of the
+  //! parent node.
+  double ParentDistance() const { return parentDistance; }
+
   /**
    * Return the specified child (0 will be left, 1 will be right).  If the index
    * is greater than 1, this will return the right child.
diff --git a/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp b/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
index 022e9f9..0fad974 100644
--- a/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
+++ b/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
@@ -29,6 +29,7 @@ BinarySpaceTree<BoundType, StatisticType, MatType>::BinarySpaceTree(
     count(data.n_cols), /* and spans all of the dataset. */
     leafSize(leafSize),
     bound(data.n_rows),
+    parentDistance(0), // Parent distance for the root is 0: it has no parent.
     dataset(data)
 {
   // Do the actual splitting of this node.
@@ -50,6 +51,7 @@ BinarySpaceTree<BoundType, StatisticType, MatType>::BinarySpaceTree(
     count(data.n_cols),
     leafSize(leafSize),
     bound(data.n_rows),
+    parentDistance(0), // Parent distance for the root is 0: it has no parent.
     dataset(data)
 {
   // Initialize oldFromNew correctly.
@@ -77,6 +79,7 @@ BinarySpaceTree<BoundType, StatisticType, MatType>::BinarySpaceTree(
     count(data.n_cols),
     leafSize(leafSize),
     bound(data.n_rows),
+    parentDistance(0), // Parent distance for the root is 0: it has no parent.
     dataset(data)
 {
   // Initialize the oldFromNew vector correctly.
@@ -212,6 +215,7 @@ BinarySpaceTree<BoundType, StatisticType, MatType>::BinarySpaceTree(
     bound(other.bound),
     stat(other.stat),
     splitDimension(other.splitDimension),
+    parentDistance(other.parentDistance),
     furthestDescendantDistance(other.furthestDescendantDistance),
     dataset(other.dataset)
 {
@@ -473,8 +477,8 @@ inline size_t BinarySpaceTree<BoundType, StatisticType, MatType>::End() const
 }
 
 template<typename BoundType, typename StatisticType, typename MatType>
-void
-    BinarySpaceTree<BoundType, StatisticType, MatType>::SplitNode(MatType& data)
+void BinarySpaceTree<BoundType, StatisticType, MatType>::SplitNode(
+    MatType& data)
 {
   // We need to expand the bounds of this node properly.
   bound |= data.cols(begin, begin + count - 1);
@@ -521,6 +525,20 @@ void
       splitCol - begin, this, leafSize);
   right = new BinarySpaceTree<BoundType, StatisticType, MatType>(data, splitCol,
       begin + count - splitCol, this, leafSize);
+
+  // Calculate parent distances for those two nodes.
+  arma::vec centroid, leftCentroid, rightCentroid;
+  Centroid(centroid);
+  left->Centroid(leftCentroid);
+  right->Centroid(rightCentroid);
+
+  const double leftParentDistance = bound.Metric().Evaluate(centroid,
+      leftCentroid);
+  const double rightParentDistance = bound.Metric().Evaluate(centroid,
+      rightCentroid);
+
+  left->ParentDistance() = leftParentDistance;
+  right->ParentDistance() = rightParentDistance;
 }
 
 template<typename BoundType, typename StatisticType, typename MatType>
@@ -574,6 +592,20 @@ void BinarySpaceTree<BoundType, StatisticType, MatType>::SplitNode(
       splitCol - begin, oldFromNew, this, leafSize);
   right = new BinarySpaceTree<BoundType, StatisticType, MatType>(data, splitCol,
       begin + count - splitCol, oldFromNew, this, leafSize);
+
+  // Calculate parent distances for those two nodes.
+  arma::vec centroid, leftCentroid, rightCentroid;
+  Centroid(centroid);
+  left->Centroid(leftCentroid);
+  right->Centroid(rightCentroid);
+
+  const double leftParentDistance = bound.Metric().Evaluate(centroid,
+      leftCentroid);
+  const double rightParentDistance = bound.Metric().Evaluate(centroid,
+      rightCentroid);
+
+  left->ParentDistance() = leftParentDistance;
+  right->ParentDistance() = rightParentDistance;
 }
 
 template<typename BoundType, typename StatisticType, typename MatType>