[mlpack-git] master, mlpack-1.0.x: Patch from Saheb: do actual naive search for RangeSearch and NeighborSearch instead of using the hack for BinarySpaceTree with leafSize = n_cols. (1f8b573)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Thu Mar 5 21:44:12 EST 2015
Repository : https://github.com/mlpack/mlpack
On branches: master,mlpack-1.0.x
Link : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40
>---------------------------------------------------------------
commit 1f8b573a604ceb0efde97e6a218fc6967380e327
Author: Ryan Curtin <ryan at ratml.org>
Date: Wed Feb 19 22:34:29 2014 +0000
Patch from Saheb: do actual naive search for RangeSearch and NeighborSearch
instead of using the hack for BinarySpaceTree with leafSize = n_cols.
>---------------------------------------------------------------
1f8b573a604ceb0efde97e6a218fc6967380e327
.../neighbor_search/neighbor_search_impl.hpp | 43 +++++++++++++-------
.../methods/range_search/range_search_impl.hpp | 46 ++++++++++++++--------
2 files changed, 58 insertions(+), 31 deletions(-)
diff --git a/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp b/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
index bc55520..3c1c697 100644
--- a/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
@@ -29,7 +29,7 @@ NeighborSearch(const typename TreeType::Mat& referenceSet,
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 @@ NeighborSearch(const typename TreeType::Mat& referenceSet,
// 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 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));
+ 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 @@ NeighborSearch(const typename TreeType::Mat& referenceSet,
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 @@ NeighborSearch(const typename TreeType::Mat& referenceSet,
// 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 @@ NeighborSearch<SortPolicy, MetricType, TreeType>::~NeighborSearch()
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;
@@ -195,7 +201,14 @@ void NeighborSearch<SortPolicy, MetricType, TreeType>::Search(
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);
diff --git a/src/mlpack/methods/range_search/range_search_impl.hpp b/src/mlpack/methods/range_search/range_search_impl.hpp
index 03afd77..061d398 100644
--- a/src/mlpack/methods/range_search/range_search_impl.hpp
+++ b/src/mlpack/methods/range_search/range_search_impl.hpp
@@ -28,7 +28,7 @@ RangeSearch<MetricType, TreeType>::RangeSearch(
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 @@ RangeSearch<MetricType, TreeType>::RangeSearch(
// 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 @@ RangeSearch<MetricType, TreeType>::RangeSearch(
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 @@ RangeSearch<MetricType, TreeType>::RangeSearch(
// 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 @@ RangeSearch<MetricType, TreeType>::~RangeSearch()
}
// 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 @@ void RangeSearch<MetricType, TreeType>::Search(
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);
More information about the mlpack-git
mailing list