[mlpack-svn] r13959 - in mlpack/trunk/src/mlpack/core/tree: binary_space_tree cover_tree
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Thu Nov 29 19:12:53 EST 2012
Author: rcurtin
Date: 2012-11-29 19:12:53 -0500 (Thu, 29 Nov 2012)
New Revision: 13959
Modified:
mlpack/trunk/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser_impl.hpp
mlpack/trunk/src/mlpack/core/tree/cover_tree/dual_tree_traverser_impl.hpp
Log:
Don't use UpdateAfterRecursion().
Modified: mlpack/trunk/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser_impl.hpp 2012-11-30 00:12:45 UTC (rev 13958)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser_impl.hpp 2012-11-30 00:12:53 UTC (rev 13959)
@@ -231,9 +231,6 @@
}
}
}
-
- // Now update any necessary information after recursion.
- rule.UpdateAfterRecursion(queryNode, referenceNode);
}
}; // namespace tree
Modified: mlpack/trunk/src/mlpack/core/tree/cover_tree/dual_tree_traverser_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/cover_tree/dual_tree_traverser_impl.hpp 2012-11-30 00:12:45 UTC (rev 13958)
+++ mlpack/trunk/src/mlpack/core/tree/cover_tree/dual_tree_traverser_impl.hpp 2012-11-30 00:12:53 UTC (rev 13959)
@@ -64,7 +64,7 @@
rootRefEntry.queryIndex = queryNode.Point();
rootRefEntry.baseCase = rule.BaseCase(queryNode.Point(),
referenceNode.Point());
- rule.UpdateAfterRecursion(queryNode, referenceNode);
+// rule.UpdateAfterRecursion(queryNode, referenceNode);
refMap[referenceNode.Scale()].push_back(rootRefEntry);
@@ -97,7 +97,9 @@
if ((queryNode.Scale() != INT_MIN) &&
(queryNode.Scale() >= (*referenceMap.rbegin()).first))
{
- // Recurse into the non-self-children first.
+ // Recurse into the non-self-children first. The recursion order cannot
+ // affect the runtime of the algorithm, because each query child recursion's
+ // results are separate and independent.
for (size_t i = 1; i < queryNode.NumChildren(); ++i)
{
std::map<int, std::vector<MapEntryType> > childMap;
@@ -167,10 +169,6 @@
// Log::Debug << "Not pruned, performing base case " << queryNode.Point() <<
// " " << pointVector[i].referenceNode->Point() << "\n";
rule.BaseCase(queryNode.Point(), pointVector[i].referenceNode->Point());
- rule.UpdateAfterRecursion(queryNode, *pointVector[i].referenceNode);
-// Log::Debug << "Bound for point " << queryNode.Point() << " scale " <<
-// queryNode.Scale() << " is now " << queryNode.Stat().Bound() <<
-// std::endl;
}
}
@@ -185,8 +183,8 @@
RootPointPolicy, StatisticType> > >& childMap)
{
// Log::Debug << "Prep for recurse into query child point " <<
-// queryNode.Child(i).Point() << " scale " << queryNode.Child(i).Scale()
-// << std::endl;
+// candidateQueryNode.Point() << " scale " <<
+// candidateQueryNode.Scale() << std::endl;
typedef DualCoverTreeMapEntry<MetricType, RootPointPolicy, StatisticType>
MapEntryType;
@@ -228,11 +226,11 @@
}
// Evaluate base case.
-// Log::Debug << "Must evaluate base case " << queryNode.Child(i).Point()
-// << " " << refNode->Point() << "\n";
+// Log::Debug << "Must evaluate base case "
+// << candidateQueryNode.Point() << " " << refNode->Point()
+// << "\n";
double baseCase = rule.BaseCase(candidateQueryNode.Point(),
refNode->Point());
- rule.UpdateAfterRecursion(candidateQueryNode, *refNode);
// Log::Debug << "Base case was " << baseCase << std::endl;
score = rule.Score(candidateQueryNode, *refNode, baseCase);
@@ -271,8 +269,8 @@
StatisticType> > >& referenceMap)
{
// Log::Debug << "Prep for recurse into query self-child point " <<
-// queryNode.Child(0).Point() << " scale " << queryNode.Child(0).Scale()
-// << std::endl;
+// candidateQueryNode.Point() << " scale " <<
+// candidateQueryNode.Scale() << std::endl;
typedef DualCoverTreeMapEntry<MetricType, RootPointPolicy, StatisticType>
MapEntryType;
@@ -281,7 +279,7 @@
// in this setting we do not recurse into any children of the reference
// entries.
typename std::map<int, std::vector<MapEntryType> >::reverse_iterator it =
- referenceMap.rbegin();
+ referenceMap.rbegin();
while (it != referenceMap.rend() && (*it).first != INT_MIN)
{
@@ -305,9 +303,9 @@
const size_t queryIndex = frame.queryIndex;
const size_t refIndex = frame.referenceIndex;
- // Log::Debug << "Recheck reference node " << refNode->Point() <<
- // " scale " << refNode->Scale() << " which has old score " <<
- // oldScore << std::endl;
+// Log::Debug << "Recheck reference node " << refNode->Point() << " scale "
+// << refNode->Scale() << " which has old score " << oldScore
+// << std::endl;
// Have we performed the base case yet?
double score;
@@ -325,12 +323,11 @@
// If not pruned, we have to perform the base case.
baseCase = rule.BaseCase(candidateQueryNode.Point(), refNode->Point());
- rule.UpdateAfterRecursion(candidateQueryNode, *refNode);
}
score = rule.Score(candidateQueryNode, *refNode, baseCase);
- // Log::Debug << "Rescored as " << score << std::endl;
+// Log::Debug << "Rescored as " << score << std::endl;
if (score == DBL_MAX)
{
@@ -339,7 +336,7 @@
continue;
}
- // Log::Debug << "Kept in map\n";
+// Log::Debug << "Kept in map\n";
// Add to child map.
newScaleVector.push_back(frame);
@@ -372,6 +369,12 @@
// the query node.
while ((*referenceMap.rbegin()).first > queryNode.Scale())
{
+ // If the query node's scale is INT_MIN and the reference map's maximum
+ // scale is INT_MIN, don't try to recurse...
+ if ((queryNode.Scale() == INT_MIN) &&
+ ((*referenceMap.rbegin()).first == INT_MIN))
+ break;
+
// Get a reference to the current largest scale.
std::vector<MapEntryType>& scaleVector = (*referenceMap.rbegin()).second;
@@ -402,7 +405,7 @@
// First we recalculate the score of this node to find if we can prune it.
if (rule.Rescore(queryNode, *refNode, score) == DBL_MAX)
{
- // Log::Warn << "Pruned after rescore\n";
+// Log::Warn << "Pruned after rescore\n";
++numPrunes;
continue;
}
@@ -416,10 +419,6 @@
// << refPoint << "\n";
baseCase = rule.BaseCase(queryNode.Point(), refPoint);
// Log::Debug << "Base case " << baseCase << std::endl;
- rule.UpdateAfterRecursion(queryNode, *refNode); // Kludgey.
-// Log::Debug << "Bound for point " << queryNode.Point() << " scale " <<
-// queryNode.Scale() << " is now " << queryNode.Stat().Bound() <<
-// std::endl;
}
// Create the score for the children.
@@ -462,7 +461,6 @@
// Calculate the base case of each child.
baseCase = rule.BaseCase(queryIndex, refIndex);
- rule.UpdateAfterRecursion(queryNode, refNode->Child(j));
// See if we can prune it.
childScore = rule.Score(queryNode, refNode->Child(j), baseCase);
More information about the mlpack-svn
mailing list