[mlpack-svn] r16217 - mlpack/trunk/src/mlpack/core/tree/binary_space_tree

[fastlab-svn at coffeetalk-1.cc.gatech.edu]

Author: rcurtin
Date: Thu Feb  6 14:55:32 2014
New Revision: 16217

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


Modified:
   mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
   mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp

Modified: mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp	Thu Feb  6 14:55:32 2014
@@ -57,6 +57,8 @@
   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 @@
    */
   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.

Modified: mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree/binary_space_tree_impl.hpp	Thu Feb  6 14:55:32 2014
@@ -29,6 +29,7 @@
     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 @@
     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 @@
     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 @@
     bound(other.bound),
     stat(other.stat),
     splitDimension(other.splitDimension),
+    parentDistance(other.parentDistance),
     furthestDescendantDistance(other.furthestDescendantDistance),
     dataset(other.dataset)
 {
@@ -473,8 +477,8 @@
 }
 
 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 @@
       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 @@
       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>