[mlpack-svn] r16312 - in mlpack/trunk/src/mlpack/methods: neighbor_search range_search
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Wed Feb 19 17:34:30 EST 2014
Author: rcurtin
Date: Wed Feb 19 17:34:29 2014
New Revision: 16312
Log:
Patch from Saheb: do actual naive search for RangeSearch and NeighborSearch
instead of using the hack for BinarySpaceTree with leafSize = n_cols.
Modified:
mlpack/trunk/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
mlpack/trunk/src/mlpack/methods/range_search/range_search_impl.hpp
Modified: mlpack/trunk/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp (original)
+++ mlpack/trunk/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp Wed Feb 19 17:34:29 2014
@@ -29,7 +29,7 @@
querySet(queryCopy),
referenceTree(NULL),
queryTree(NULL),
- treeOwner(true), // False if a tree was passed.
+ treeOwner(!naive), // False if a tree was passed. If naive, then no trees.
hasQuerySet(true),
naive(naive),
singleMode(!naive && singleMode), // No single mode if naive.
@@ -42,13 +42,16 @@
// We'll time tree building, but only if we are building trees.
Timer::Start("tree_building");
- // Construct as a naive object if we need to.
- referenceTree = new TreeType(referenceCopy, oldFromNewReferences,
- (naive ? referenceCopy.n_cols : leafSize));
-
- if (!singleMode)
- queryTree = new TreeType(queryCopy, oldFromNewQueries,
- (naive ? querySet.n_cols : leafSize));
+ // If not in naive mode, then we need to build trees.
+ if (!naive)
+ {
+ referenceTree = new TreeType(referenceCopy, oldFromNewReferences,
+ (naive ? referenceCopy.n_cols : leafSize));
+
+ if (!singleMode)
+ queryTree = new TreeType(queryCopy, oldFromNewQueries,
+ (naive ? querySet.n_cols : leafSize));
+ }
// Stop the timer we started above (if we need to).
Timer::Stop("tree_building");
@@ -67,7 +70,7 @@
querySet(referenceCopy),
referenceTree(NULL),
queryTree(NULL),
- treeOwner(true),
+ treeOwner(!naive), // If naive, then we are not building any trees.
hasQuerySet(false),
naive(naive),
singleMode(!naive && singleMode), // No single mode if naive.
@@ -77,11 +80,14 @@
// We'll time tree building, but only if we are building trees.
Timer::Start("tree_building");
- // Construct as a naive object if we need to.
- referenceTree = new TreeType(referenceCopy, oldFromNewReferences,
- (naive ? referenceSet.n_cols : leafSize));
- if (!singleMode)
- queryTree = new TreeType(*referenceTree);
+ // If not in naive mode, then we may need to construct trees.
+ if (!naive)
+ {
+ referenceTree = new TreeType(referenceCopy, oldFromNewReferences,
+ (naive ? referenceSet.n_cols : leafSize));
+ if (!singleMode)
+ queryTree = new TreeType(*referenceTree);
+ }
// Stop the timer we started above.
Timer::Stop("tree_building");
@@ -151,7 +157,7 @@
if (queryTree)
delete queryTree;
}
- else if (!treeOwner && !hasQuerySet && !singleMode)
+ else if (!treeOwner && !hasQuerySet && !(singleMode || naive))
{
// We replicated the reference tree to create a query tree.
delete queryTree;
@@ -187,7 +193,7 @@
neighborPtr->fill(size_t() - 1);
distancePtr->set_size(k, querySet.n_cols);
distancePtr->fill(SortPolicy::WorstDistance());
-
+
// compiler flags this as unused.
//size_t numPrunes = 0;
@@ -195,7 +201,14 @@
typedef NeighborSearchRules<SortPolicy, MetricType, TreeType> RuleType;
RuleType rules(referenceSet, querySet, *neighborPtr, *distancePtr, metric);
- if (singleMode)
+ if (naive)
+ {
+ // The naive brute-force traversal.
+ for (size_t i = 0; i < querySet.n_cols; ++i)
+ for (size_t j = 0; j < referenceSet.n_cols; ++j)
+ rules.BaseCase(i, j);
+ }
+ else if (singleMode)
{
// Create the traverser.
typename TreeType::template SingleTreeTraverser<RuleType> traverser(rules);
@@ -297,7 +310,7 @@
convert << " Reference Set: " << referenceSet.n_rows << "x" ;
convert << referenceSet.n_cols << std::endl;
if (&referenceSet != &querySet)
- convert << " QuerySet: " << querySet.n_rows << "x" << querySet.n_cols
+ convert << " QuerySet: " << querySet.n_rows << "x" << querySet.n_cols
<< std::endl;
convert << " Reference Tree: " << referenceTree << std::endl;
if (&referenceTree != &queryTree)
Modified: mlpack/trunk/src/mlpack/methods/range_search/range_search_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/methods/range_search/range_search_impl.hpp (original)
+++ mlpack/trunk/src/mlpack/methods/range_search/range_search_impl.hpp Wed Feb 19 17:34:29 2014
@@ -28,7 +28,7 @@
queryCopy(querySet),
referenceSet(referenceCopy),
querySet(queryCopy),
- treeOwner(true),
+ treeOwner(!naive), // If in naive mode, we are not building any trees.
hasQuerySet(true),
naive(naive),
singleMode(!naive && singleMode), // Naive overrides single mode.
@@ -38,12 +38,17 @@
// Build the trees.
Timer::Start("range_search/tree_building");
- // Naive sets the leaf size such that the entire tree is one node.
- referenceTree = new TreeType(referenceCopy, oldFromNewReferences,
- (naive ? referenceCopy.n_cols : leafSize));
+ // If in naive mode, then we do not need to build trees.
+ if (!naive)
+ {
+ referenceTree = new TreeType(referenceCopy, oldFromNewReferences,
+ (naive ? referenceCopy.n_cols : leafSize));
- queryTree = new TreeType(queryCopy, oldFromNewQueries,
- (naive ? queryCopy.n_cols : leafSize));
+ // If we are in dual-tree mode, we need to build a query tree too.
+ if (!singleMode)
+ queryTree = new TreeType(queryCopy, oldFromNewQueries,
+ (naive ? queryCopy.n_cols : leafSize));
+ }
Timer::Stop("range_search/tree_building");
}
@@ -59,7 +64,7 @@
referenceSet(referenceCopy),
querySet(referenceCopy),
queryTree(NULL),
- treeOwner(true),
+ treeOwner(!naive), // If in naive mode, we are not building any trees.
hasQuerySet(false),
naive(naive),
singleMode(!naive && singleMode), // Naive overrides single mode.
@@ -69,14 +74,16 @@
// Build the trees.
Timer::Start("range_search/tree_building");
- // Naive sets the leaf size such that the entire tree is one node.
- referenceTree = new TreeType(referenceCopy, oldFromNewReferences,
- (naive ? referenceCopy.n_cols : leafSize));
-
- // If using dual-tree mode, then we need a second tree.
- if (!singleMode)
- queryTree = new TreeType(*referenceTree);
+ // If in naive mode, then we do not need to build trees.
+ if (!naive)
+ {
+ referenceTree = new TreeType(referenceCopy, oldFromNewReferences,
+ (naive ? referenceCopy.n_cols : leafSize));
+ // If using dual-tree mode, then we need a second tree.
+ if (!singleMode)
+ queryTree = new TreeType(*referenceTree);
+ }
Timer::Stop("range_search/tree_building");
}
@@ -136,7 +143,7 @@
}
// If doing dual-tree search with one dataset, we cloned the reference tree.
- if (!treeOwner && !hasQuerySet && !singleMode)
+ if (!treeOwner && !hasQuerySet && !(singleMode || naive))
delete queryTree;
}
@@ -174,7 +181,14 @@
RuleType rules(referenceSet, querySet, range, *neighborPtr, *distancePtr,
metric);
- if (singleMode)
+ if (naive)
+ {
+ // The naive brute-force solution.
+ for (size_t i = 0; i < querySet.n_cols; ++i)
+ for (size_t j = 0; j < referenceSet.n_cols; ++j)
+ rules.BaseCase(i, j);
+ }
+ else if (singleMode)
{
// Create the traverser.
typename TreeType::template SingleTreeTraverser<RuleType> traverser(rules);
@@ -282,11 +296,11 @@
{
std::ostringstream convert;
convert << "Range Search [" << this << "]" << std::endl;
- if (treeOwner)
+ if (treeOwner)
convert << " Tree Owner: TRUE" << std::endl;
- if (naive)
+ if (naive)
convert << " Naive: TRUE" << std::endl;
- convert << " Metric: " << std::endl <<
+ convert << " Metric: " << std::endl <<
mlpack::util::Indent(metric.ToString(),2);
return convert.str();
}
More information about the mlpack-svn
mailing list