[mlpack-svn] r13974 - mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies

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

Author: rcurtin
Date: 2012-12-04 18:22:13 -0500 (Tue, 04 Dec 2012)
New Revision: 13974

Modified:
   mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.hpp
   mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort_impl.hpp
   mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp
   mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort_impl.hpp
Log:
Add function for cover tree pruning.


Modified: mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.hpp
===================================================================
--- mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.hpp	2012-12-04 21:55:14 UTC (rev 13973)
+++ mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.hpp	2012-12-04 23:22:13 UTC (rev 13974)
@@ -73,6 +73,24 @@
                                        const double centerToCenterDistance);
 
   /**
+   * Return the best possible distance between the query node and the reference
+   * child node given the base case distance between the query node and the
+   * reference node.  TreeType::ParentDistance() must be implemented to use
+   * this.
+   *
+   * @param queryNode Query node.
+   * @param referenceNode Reference node.
+   * @param referenceChildNode Child of reference node which is being inspected.
+   * @param centerToCenterDistance Distance between centers of query node and
+   *     reference node.
+   */
+  template<typename TreeType>
+  static double BestNodeToNodeDistance(const TreeType* queryNode,
+                                       const TreeType* referenceNode,
+                                       const TreeType* referenceChildNode,
+                                       const double centerToCenterDistance);
+
+  /**
    * Return the best possible distance between a node and a point.  In our case,
    * this is the maximum distance between the tree node and the point using the
    * given distance function.

Modified: mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort_impl.hpp	2012-12-04 21:55:14 UTC (rev 13973)
+++ mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort_impl.hpp	2012-12-04 23:22:13 UTC (rev 13974)
@@ -31,6 +31,17 @@
 }
 
 template<typename TreeType>
+inline double FurthestNeighborSort::BestNodeToNodeDistance(
+    const TreeType* queryNode,
+    const TreeType* referenceNode,
+    const TreeType* referenceChildNode,
+    const double centerToCenterDistance)
+{
+  return queryNode->MaxDistance(referenceNode, centerToCenterDistance) +
+      referenceChildNode->ParentDistance();
+}
+
+template<typename TreeType>
 inline double FurthestNeighborSort::BestPointToNodeDistance(
     const arma::vec& point,
     const TreeType* referenceNode)

Modified: mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp
===================================================================
--- mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp	2012-12-04 21:55:14 UTC (rev 13973)
+++ mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp	2012-12-04 23:22:13 UTC (rev 13974)
@@ -75,7 +75,25 @@
   static double BestNodeToNodeDistance(const TreeType* queryNode,
                                        const TreeType* referenceNode,
                                        const double centerToCenterDistance);
+
   /**
+   * Return the best possible distance between the query node and the reference
+   * child node given the base case distance between the query node and the
+   * reference node.  TreeType::ParentDistance() must be implemented to use
+   * this.
+   *
+   * @param queryNode Query node.
+   * @param referenceNode Reference node.
+   * @param referenceChildNode Child of reference node which is being inspected.
+   * @param centerToCenterDistance Distance between centers of query node and
+   *     reference node.
+   */
+  template<typename TreeType>
+  static double BestNodeToNodeDistance(const TreeType* queryNode,
+                                       const TreeType* referenceNode,
+                                       const TreeType* referenceChildNode,
+                                       const double centerToCenterDistance);
+  /**
    * Return the best possible distance between a node and a point.  In our case,
    * this is the minimum distance between the tree node and the point using the
    * given distance function.

Modified: mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort_impl.hpp	2012-12-04 21:55:14 UTC (rev 13973)
+++ mlpack/trunk/src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort_impl.hpp	2012-12-04 23:22:13 UTC (rev 13974)
@@ -31,6 +31,17 @@
 }
 
 template<typename TreeType>
+inline double NearestNeighborSort::BestNodeToNodeDistance(
+    const TreeType* queryNode,
+    const TreeType* /* referenceNode */,
+    const TreeType* referenceChildNode,
+    const double centerToCenterDistance)
+{
+  return queryNode->MinDistance(referenceChildNode, centerToCenterDistance) -
+      referenceChildNode->ParentDistance();
+}
+
+template<typename TreeType>
 inline double NearestNeighborSort::BestPointToNodeDistance(
     const arma::vec& point,
     const TreeType* referenceNode)