[mlpack-svn] r13354 - mlpack/trunk/src/mlpack/core/tree/cover_tree

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

Author: rcurtin
Date: 2012-08-07 01:26:02 -0400 (Tue, 07 Aug 2012)
New Revision: 13354

Modified:
   mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp
   mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp
Log:
Add new methods for finding the maximum or minimum distance to a point or node
if the distance between the point and node center (or node center and node
center) is already known.


Modified: mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp	2012-08-06 21:19:23 UTC (rev 13353)
+++ mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree.hpp	2012-08-07 05:26:02 UTC (rev 13354)
@@ -207,15 +207,31 @@
   //! Return the minimum distance to another node.
   double MinDistance(const CoverTree* other) const;
 
+  //! Return the minimum distance to another node given that the point-to-point
+  //! distance has already been calculated.
+  double MinDistance(const CoverTree* other, const double distance) const;
+
   //! Return the minimum distance to another point.
   double MinDistance(const arma::vec& other) const;
 
+  //! Return the minimum distance to another point given that the distance from
+  //! the center to the point has already been calculated.
+  double MinDistance(const arma::vec& other, const double distance) const;
+
   //! Return the maximum distance to another node.
   double MaxDistance(const CoverTree* other) const;
 
+  //! Return the maximum distance to another node given that the point-to-point
+  //! distance has already been calculated.
+  double MaxDistance(const CoverTree* other, const double distance) const;
+
   //! Return the maximum distance to another point.
   double MaxDistance(const arma::vec& other) const;
 
+  //! Return the maximum distance to another point given that the distance from
+  //! the center to the point has already been calculated.
+  double MaxDistance(const arma::vec& other, const double distance) const;
+
   //! Returns true: this tree does have self-children.
   static bool HasSelfChildren() { return true; }
 

Modified: mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp	2012-08-06 21:19:23 UTC (rev 13353)
+++ mlpack/trunk/src/mlpack/core/tree/cover_tree/cover_tree_impl.hpp	2012-08-07 05:26:02 UTC (rev 13354)
@@ -424,21 +424,39 @@
     const CoverTree<MetricType, RootPointPolicy, StatisticType>* other) const
 {
   // Every cover tree node will contain points up to EC^(scale + 1) away.
-  return MetricType::Evaluate(dataset.unsafe_col(point),
+  return std::max(MetricType::Evaluate(dataset.unsafe_col(point),
       other->Dataset().unsafe_col(other->Point())) -
       std::pow(expansionConstant, scale + 1) -
-      std::pow(other->ExpansionConstant(), other->Scale() + 1);
+      std::pow(other->ExpansionConstant(), other->Scale() + 1), 0.0);
 }
 
 template<typename MetricType, typename RootPointPolicy, typename StatisticType>
 double CoverTree<MetricType, RootPointPolicy, StatisticType>::MinDistance(
+    const CoverTree<MetricType, RootPointPolicy, StatisticType>* other,
+    const double distance) const
+{
+  // We already have the distance as evaluated by the metric.
+  return std::max(distance - (std::pow(expansionConstant, scale + 1) -
+      std::pow(other->ExpansionConstant(), other->Scale() + 1)), 0.0);
+}
+
+template<typename MetricType, typename RootPointPolicy, typename StatisticType>
+double CoverTree<MetricType, RootPointPolicy, StatisticType>::MinDistance(
     const arma::vec& other) const
 {
-  return MetricType::Evaluate(dataset.unsafe_col(point), other) -
-      std::pow(expansionConstant, scale + 1);
+  return std::max(MetricType::Evaluate(dataset.unsafe_col(point), other) -
+      std::pow(expansionConstant, scale + 1), 0.0);
 }
 
 template<typename MetricType, typename RootPointPolicy, typename StatisticType>
+double CoverTree<MetricType, RootPointPolicy, StatisticType>::MinDistance(
+    const arma::vec& other,
+    const double distance) const
+{
+  return std::max(distance - std::pow(expansionConstant, scale + 1), 0.0);
+}
+
+template<typename MetricType, typename RootPointPolicy, typename StatisticType>
 double CoverTree<MetricType, RootPointPolicy, StatisticType>::MaxDistance(
     const CoverTree<MetricType, RootPointPolicy, StatisticType>* other) const
 {
@@ -450,6 +468,16 @@
 
 template<typename MetricType, typename RootPointPolicy, typename StatisticType>
 double CoverTree<MetricType, RootPointPolicy, StatisticType>::MaxDistance(
+    const CoverTree<MetricType, RootPointPolicy, StatisticType>* other,
+    const double distance) const
+{
+  // We already have the distance as evaluated by the metric.
+  return distance + (std::pow(expansionConstant, scale + 1) +
+      std::pow(other->ExpansionConstant(), other->Scale() + 1));
+}
+
+template<typename MetricType, typename RootPointPolicy, typename StatisticType>
+double CoverTree<MetricType, RootPointPolicy, StatisticType>::MaxDistance(
     const arma::vec& other) const
 {
   return MetricType::Evaluate(dataset.unsafe_col(point), other) +
@@ -457,6 +485,14 @@
 }
 
 template<typename MetricType, typename RootPointPolicy, typename StatisticType>
+double CoverTree<MetricType, RootPointPolicy, StatisticType>::MaxDistance(
+    const arma::vec& other,
+    const double distance) const
+{
+  return distance + std::pow(expansionConstant, scale + 1);
+}
+
+template<typename MetricType, typename RootPointPolicy, typename StatisticType>
 size_t CoverTree<MetricType, RootPointPolicy, StatisticType>::SplitNearFar(
     arma::Col<size_t>& indices,
     arma::vec& distances,