[mlpack-git] master: Properly define the Tree Traversers for Spill trees. (0267acb)
gitdub at mlpack.org
gitdub at mlpack.org
Wed Aug 17 00:07:52 EDT 2016
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/0f4b25acd6aaa14294c044874ba6cc0751712baa...0a19d07bd39e6223991976474bc79671ba8aa0f0
>---------------------------------------------------------------
commit 0267acb46caef51370e737cf253a1664ea7be263
Author: MarcosPividori <marcos.pividori at gmail.com>
Date: Wed Aug 17 01:07:52 2016 -0300
Properly define the Tree Traversers for Spill trees.
>---------------------------------------------------------------
0267acb46caef51370e737cf253a1664ea7be263
src/mlpack/core/tree/CMakeLists.txt | 8 +++---
src/mlpack/core/tree/spill_tree.hpp | 8 +++---
...traverser.hpp => spill_dual_tree_traverser.hpp} | 20 +++++++-------
...impl.hpp => spill_dual_tree_traverser_impl.hpp} | 27 ++++++++++---------
...averser.hpp => spill_single_tree_traverser.hpp} | 16 ++++++-----
...pl.hpp => spill_single_tree_traverser_impl.hpp} | 19 ++++++-------
src/mlpack/core/tree/spill_tree/spill_tree.hpp | 31 ++++++++++++++++++----
7 files changed, 78 insertions(+), 51 deletions(-)
diff --git a/src/mlpack/core/tree/CMakeLists.txt b/src/mlpack/core/tree/CMakeLists.txt
index 546c22a..34dc5c7 100644
--- a/src/mlpack/core/tree/CMakeLists.txt
+++ b/src/mlpack/core/tree/CMakeLists.txt
@@ -90,10 +90,10 @@ set(SOURCES
spill_tree.hpp
spill_tree/spill_tree.hpp
spill_tree/spill_tree_impl.hpp
- spill_tree/dual_tree_traverser.hpp
- spill_tree/dual_tree_traverser_impl.hpp
- spill_tree/single_tree_traverser.hpp
- spill_tree/single_tree_traverser_impl.hpp
+ spill_tree/spill_dual_tree_traverser.hpp
+ spill_tree/spill_dual_tree_traverser_impl.hpp
+ spill_tree/spill_single_tree_traverser.hpp
+ spill_tree/spill_single_tree_traverser_impl.hpp
spill_tree/traits.hpp
spill_tree/typedef.hpp
statistic.hpp
diff --git a/src/mlpack/core/tree/spill_tree.hpp b/src/mlpack/core/tree/spill_tree.hpp
index 589e845..b93300b 100644
--- a/src/mlpack/core/tree/spill_tree.hpp
+++ b/src/mlpack/core/tree/spill_tree.hpp
@@ -10,10 +10,10 @@
#include <mlpack/core.hpp>
#include "bounds.hpp"
#include "spill_tree/spill_tree.hpp"
-#include "spill_tree/single_tree_traverser.hpp"
-#include "spill_tree/single_tree_traverser_impl.hpp"
-#include "spill_tree/dual_tree_traverser.hpp"
-#include "spill_tree/dual_tree_traverser_impl.hpp"
+#include "spill_tree/spill_single_tree_traverser.hpp"
+#include "spill_tree/spill_single_tree_traverser_impl.hpp"
+#include "spill_tree/spill_dual_tree_traverser.hpp"
+#include "spill_tree/spill_dual_tree_traverser_impl.hpp"
#include "spill_tree/traits.hpp"
#include "spill_tree/typedef.hpp"
diff --git a/src/mlpack/core/tree/spill_tree/dual_tree_traverser.hpp b/src/mlpack/core/tree/spill_tree/spill_dual_tree_traverser.hpp
similarity index 81%
rename from src/mlpack/core/tree/spill_tree/dual_tree_traverser.hpp
rename to src/mlpack/core/tree/spill_tree/spill_dual_tree_traverser.hpp
index a1ee86e..0e3b732 100644
--- a/src/mlpack/core/tree/spill_tree/dual_tree_traverser.hpp
+++ b/src/mlpack/core/tree/spill_tree/spill_dual_tree_traverser.hpp
@@ -1,15 +1,17 @@
/**
- * @file dual_tree_traverser.hpp
+ * @file spill_dual_tree_traverser.hpp
* @author Ryan Curtin
* @author Marcos Pividori
*
- * Defines the DualTreeTraverser for the SpillTree tree type. This is a
+ * Defines the SpillDualTreeTraverser for the SpillTree tree type. This is a
* nested class of SpillTree which traverses two trees in a depth-first
* manner with a given set of rules which indicate the branches which can be
* pruned and the order in which to recurse.
+ * The Defeatist template parameter determines if the traversers must do
+ * defeatist search on overlapping nodes.
*/
-#ifndef MLPACK_CORE_TREE_SPILL_TREE_DUAL_TREE_TRAVERSER_HPP
-#define MLPACK_CORE_TREE_SPILL_TREE_DUAL_TREE_TRAVERSER_HPP
+#ifndef MLPACK_CORE_TREE_SPILL_TREE_SPILL_DUAL_TREE_TRAVERSER_HPP
+#define MLPACK_CORE_TREE_SPILL_TREE_SPILL_DUAL_TREE_TRAVERSER_HPP
#include <mlpack/core.hpp>
@@ -24,15 +26,15 @@ template<typename MetricType,
template<typename HyperplaneMetricType> class HyperplaneType,
template<typename SplitMetricType, typename SplitMatType>
class SplitType>
-template<typename RuleType>
+template<typename RuleType, bool Defeatist>
class SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>::
- DualTreeTraverser
+ SpillDualTreeTraverser
{
public:
/**
* Instantiate the dual-tree traverser with the given rule set.
*/
- DualTreeTraverser(RuleType& rule);
+ SpillDualTreeTraverser(RuleType& rule);
/**
* Traverse the two trees. This does not reset the number of prunes.
@@ -89,7 +91,7 @@ class SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>::
} // namespace mlpack
// Include implementation.
-#include "dual_tree_traverser_impl.hpp"
+#include "spill_dual_tree_traverser_impl.hpp"
-#endif // MLPACK_CORE_TREE_SPILL_TREE_DUAL_TREE_TRAVERSER_HPP
+#endif // MLPACK_CORE_TREE_SPILL_TREE_SPILL_DUAL_TREE_TRAVERSER_HPP
diff --git a/src/mlpack/core/tree/spill_tree/dual_tree_traverser_impl.hpp b/src/mlpack/core/tree/spill_tree/spill_dual_tree_traverser_impl.hpp
similarity index 94%
rename from src/mlpack/core/tree/spill_tree/dual_tree_traverser_impl.hpp
rename to src/mlpack/core/tree/spill_tree/spill_dual_tree_traverser_impl.hpp
index c85d211..c6deca2 100644
--- a/src/mlpack/core/tree/spill_tree/dual_tree_traverser_impl.hpp
+++ b/src/mlpack/core/tree/spill_tree/spill_dual_tree_traverser_impl.hpp
@@ -1,17 +1,17 @@
/**
- * @file dual_tree_traverser_impl.hpp
+ * @file spill_dual_tree_traverser_impl.hpp
* @author Ryan Curtin
* @author Marcos Pividori
*
- * Implementation of the DualTreeTraverser for SpillTree. This is a way
+ * Implementation of the SpillDualTreeTraverser for SpillTree. This is a way
* to perform a dual-tree traversal of two trees. The trees must be the same
* type.
*/
-#ifndef MLPACK_CORE_TREE_SPILL_TREE_DUAL_TREE_TRAVERSER_IMPL_HPP
-#define MLPACK_CORE_TREE_SPILL_TREE_DUAL_TREE_TRAVERSER_IMPL_HPP
+#ifndef MLPACK_CORE_TREE_SPILL_TREE_SPILL_DUAL_TREE_TRAVERSER_IMPL_HPP
+#define MLPACK_CORE_TREE_SPILL_TREE_SPILL_DUAL_TREE_TRAVERSER_IMPL_HPP
// In case it hasn't been included yet.
-#include "dual_tree_traverser.hpp"
+#include "spill_dual_tree_traverser.hpp"
namespace mlpack {
namespace tree {
@@ -22,9 +22,10 @@ template<typename MetricType,
template<typename HyperplaneMetricType> class HyperplaneType,
template<typename SplitMetricType, typename SplitMatType>
class SplitType>
-template<typename RuleType>
+template<typename RuleType, bool Defeatist>
SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>::
-DualTreeTraverser<RuleType>::DualTreeTraverser(RuleType& rule) :
+SpillDualTreeTraverser<RuleType, Defeatist>::SpillDualTreeTraverser(
+ RuleType& rule) :
rule(rule),
numPrunes(0),
numVisited(0),
@@ -38,9 +39,9 @@ template<typename MetricType,
template<typename HyperplaneMetricType> class HyperplaneType,
template<typename SplitMetricType, typename SplitMatType>
class SplitType>
-template<typename RuleType>
+template<typename RuleType, bool Defeatist>
void SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>::
-DualTreeTraverser<RuleType>::Traverse(
+SpillDualTreeTraverser<RuleType, Defeatist>::Traverse(
SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>&
queryNode,
SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>&
@@ -155,7 +156,7 @@ DualTreeTraverser<RuleType>::Traverse(
}
else
{
- if (referenceNode.Overlap())
+ if (Defeatist && referenceNode.Overlap())
{
// If referenceNode is a overlapping node and we can't decide which
// child node to traverse, this means that queryNode is at both sides
@@ -259,7 +260,7 @@ DualTreeTraverser<RuleType>::Traverse(
}
else
{
- if (referenceNode.Overlap())
+ if (Defeatist && referenceNode.Overlap())
{
// If referenceNode is a overlapping node and we can't decide which
// child node to traverse, this means that queryNode.Left() is at both
@@ -348,7 +349,7 @@ DualTreeTraverser<RuleType>::Traverse(
}
else
{
- if (referenceNode.Overlap())
+ if (Defeatist && referenceNode.Overlap())
{
// If referenceNode is a overlapping node and we can't decide which
// child node to traverse, this means that queryNode.Right() is at
@@ -385,4 +386,4 @@ DualTreeTraverser<RuleType>::Traverse(
} // namespace tree
} // namespace mlpack
-#endif // MLPACK_CORE_TREE_SPILL_TREE_DUAL_TREE_TRAVERSER_IMPL_HPP
+#endif // MLPACK_CORE_TREE_SPILL_TREE_SPILL_DUAL_TREE_TRAVERSER_IMPL_HPP
diff --git a/src/mlpack/core/tree/spill_tree/single_tree_traverser.hpp b/src/mlpack/core/tree/spill_tree/spill_single_tree_traverser.hpp
similarity index 77%
rename from src/mlpack/core/tree/spill_tree/single_tree_traverser.hpp
rename to src/mlpack/core/tree/spill_tree/spill_single_tree_traverser.hpp
index 3d648cf..e2debe5 100644
--- a/src/mlpack/core/tree/spill_tree/single_tree_traverser.hpp
+++ b/src/mlpack/core/tree/spill_tree/spill_single_tree_traverser.hpp
@@ -1,14 +1,16 @@
/**
- * @file single_tree_traverser.hpp
+ * @file spill_single_tree_traverser.hpp
* @author Ryan Curtin
* @author Marcos Pividori
*
* A nested class of SpillTree which traverses the entire tree with a
* given set of rules which indicate the branches which can be pruned and the
* order in which to recurse. This traverser is a depth-first traverser.
+ * The Defeatist template parameter determines if the traversers must do
+ * defeatist search on overlapping nodes.
*/
-#ifndef MLPACK_CORE_TREE_SPILL_TREE_SINGLE_TREE_TRAVERSER_HPP
-#define MLPACK_CORE_TREE_SPILL_TREE_SINGLE_TREE_TRAVERSER_HPP
+#ifndef MLPACK_CORE_TREE_SPILL_TREE_SPILL_SINGLE_TREE_TRAVERSER_HPP
+#define MLPACK_CORE_TREE_SPILL_TREE_SPILL_SINGLE_TREE_TRAVERSER_HPP
#include <mlpack/core.hpp>
@@ -23,15 +25,15 @@ template<typename MetricType,
template<typename HyperplaneMetricType> class HyperplaneType,
template<typename SplitMetricType, typename SplitMatType>
class SplitType>
-template<typename RuleType>
+template<typename RuleType, bool Defeatist>
class SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>::
- SingleTreeTraverser
+ SpillSingleTreeTraverser
{
public:
/**
* Instantiate the single tree traverser with the given rule set.
*/
- SingleTreeTraverser(RuleType& rule);
+ SpillSingleTreeTraverser(RuleType& rule);
/**
* Traverse the tree with the given point.
@@ -59,6 +61,6 @@ class SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>::
} // namespace mlpack
// Include implementation.
-#include "single_tree_traverser_impl.hpp"
+#include "spill_single_tree_traverser_impl.hpp"
#endif
diff --git a/src/mlpack/core/tree/spill_tree/single_tree_traverser_impl.hpp b/src/mlpack/core/tree/spill_tree/spill_single_tree_traverser_impl.hpp
similarity index 88%
rename from src/mlpack/core/tree/spill_tree/single_tree_traverser_impl.hpp
rename to src/mlpack/core/tree/spill_tree/spill_single_tree_traverser_impl.hpp
index 3aca649..4ce5a22 100644
--- a/src/mlpack/core/tree/spill_tree/single_tree_traverser_impl.hpp
+++ b/src/mlpack/core/tree/spill_tree/spill_single_tree_traverser_impl.hpp
@@ -1,5 +1,5 @@
/**
- * @file single_tree_traverser_impl.hpp
+ * @file spill_single_tree_traverser_impl.hpp
* @author Ryan Curtin
* @author Marcos Pividori
*
@@ -7,11 +7,11 @@
* given set of rules which indicate the branches which can be pruned and the
* order in which to recurse. This traverser is a depth-first traverser.
*/
-#ifndef MLPACK_CORE_TREE_SPILL_TREE_SINGLE_TREE_TRAVERSER_IMPL_HPP
-#define MLPACK_CORE_TREE_SPILL_TREE_SINGLE_TREE_TRAVERSER_IMPL_HPP
+#ifndef MLPACK_CORE_TREE_SPILL_TREE_SPILL_SINGLE_TREE_TRAVERSER_IMPL_HPP
+#define MLPACK_CORE_TREE_SPILL_TREE_SPILL_SINGLE_TREE_TRAVERSER_IMPL_HPP
// In case it hasn't been included yet.
-#include "single_tree_traverser.hpp"
+#include "spill_single_tree_traverser.hpp"
namespace mlpack {
namespace tree {
@@ -22,9 +22,10 @@ template<typename MetricType,
template<typename HyperplaneMetricType> class HyperplaneType,
template<typename SplitMetricType, typename SplitMatType>
class SplitType>
-template<typename RuleType>
+template<typename RuleType, bool Defeatist>
SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>::
-SingleTreeTraverser<RuleType>::SingleTreeTraverser(RuleType& rule) :
+SpillSingleTreeTraverser<RuleType, Defeatist>::SpillSingleTreeTraverser(
+ RuleType& rule) :
rule(rule),
numPrunes(0)
{ /* Nothing to do. */ }
@@ -35,9 +36,9 @@ template<typename MetricType,
template<typename HyperplaneMetricType> class HyperplaneType,
template<typename SplitMetricType, typename SplitMatType>
class SplitType>
-template<typename RuleType>
+template<typename RuleType, bool Defeatist>
void SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>::
-SingleTreeTraverser<RuleType>::Traverse(
+SpillSingleTreeTraverser<RuleType, Defeatist>::Traverse(
const size_t queryIndex,
SpillTree<MetricType, StatisticType, MatType, HyperplaneType, SplitType>&
referenceNode)
@@ -50,7 +51,7 @@ SingleTreeTraverser<RuleType>::Traverse(
}
else
{
- if (referenceNode.Overlap())
+ if (Defeatist && referenceNode.Overlap())
{
// If referenceNode is a overlapping node we do defeatist search. In this
// case, it is enough to calculate the score of only one child node. As we
diff --git a/src/mlpack/core/tree/spill_tree/spill_tree.hpp b/src/mlpack/core/tree/spill_tree/spill_tree.hpp
index 24c97f2..eb2cdcf 100644
--- a/src/mlpack/core/tree/spill_tree/spill_tree.hpp
+++ b/src/mlpack/core/tree/spill_tree/spill_tree.hpp
@@ -109,15 +109,36 @@ class SpillTree
//! If true, we own the dataset and need to destroy it in the destructor.
bool localDataset;
+ //! A generic single-tree traverser for hybrid spill trees; see
+ //! spill_single_tree_traverser.hpp for implementation. The Defeatist
+ //! template parameter determines if the traverser must do defeatist search on
+ //! overlapping nodes.
+ template<typename RuleType, bool Defeatist = false>
+ class SpillSingleTreeTraverser;
+
+ //! A generic dual-tree traverser for hybrid spill trees; see
+ //! spill_dual_tree_traverser.hpp for implementation. The Defeatist
+ //! template parameter determines if the traverser must do defeatist search on
+ //! overlapping nodes.
+ template<typename RuleType, bool Defeatist = false>
+ class SpillDualTreeTraverser;
+
public:
- //! A single-tree traverser for hybrid spill trees; see
- //! single_tree_traverser.hpp for implementation.
+ //! A single-tree traverser for hybrid spill trees.
+ template<typename RuleType>
+ using SingleTreeTraverser = SpillSingleTreeTraverser<RuleType, false>;
+
+ //! A defeatist single-tree traverser for hybrid spill trees.
+ template<typename RuleType>
+ using DefeatistSingleTreeTraverser = SpillSingleTreeTraverser<RuleType, true>;
+
+ //! A dual-tree traverser for hybrid spill trees.
template<typename RuleType>
- class SingleTreeTraverser;
+ using DualTreeTraverser = SpillDualTreeTraverser<RuleType, false>;
- //! A dual-tree traverser for hybrid spill trees; see dual_tree_traverser.hpp.
+ //! A defeatist dual-tree traverser for hybrid spill trees.
template<typename RuleType>
- class DualTreeTraverser;
+ using DefeatistDualTreeTraverser = SpillDualTreeTraverser<RuleType, true>;
/**
* Construct this as the root node of a hybrid spill tree using the given
More information about the mlpack-git
mailing list