[mlpack-git] master: Add support for Hybrid SP-Tree Search (Single tree traverser). (8d5994c)
gitdub at mlpack.org
gitdub at mlpack.org
Thu Aug 18 13:39:17 EDT 2016
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/0f4b25acd6aaa14294c044874ba6cc0751712baa...0a19d07bd39e6223991976474bc79671ba8aa0f0
>---------------------------------------------------------------
commit 8d5994cf281e0bec9fdc3ebef3859e2cfe8eb5e7
Author: MarcosPividori <marcos.pividori at gmail.com>
Date: Tue Jul 12 20:51:02 2016 -0300
Add support for Hybrid SP-Tree Search (Single tree traverser).
>---------------------------------------------------------------
8d5994cf281e0bec9fdc3ebef3859e2cfe8eb5e7
src/mlpack/core/tree/CMakeLists.txt | 4 ++
src/mlpack/core/tree/spill_tree.hpp | 4 ++
.../dual_tree_traverser.hpp | 19 ++++----
.../tree/spill_tree/dual_tree_traverser_impl.hpp | 57 ++++++++++++++++++++++
.../single_tree_traverser.hpp | 17 ++++---
.../single_tree_traverser_impl.hpp | 46 ++++++++++++-----
src/mlpack/core/tree/spill_tree/spill_tree.hpp | 6 +--
7 files changed, 122 insertions(+), 31 deletions(-)
diff --git a/src/mlpack/core/tree/CMakeLists.txt b/src/mlpack/core/tree/CMakeLists.txt
index d8fc99c..42cf411 100644
--- a/src/mlpack/core/tree/CMakeLists.txt
+++ b/src/mlpack/core/tree/CMakeLists.txt
@@ -78,6 +78,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/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 9732ab2..589e845 100644
--- a/src/mlpack/core/tree/spill_tree.hpp
+++ b/src/mlpack/core/tree/spill_tree.hpp
@@ -10,6 +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/traits.hpp"
#include "spill_tree/typedef.hpp"
diff --git a/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser.hpp b/src/mlpack/core/tree/spill_tree/dual_tree_traverser.hpp
similarity index 81%
copy from src/mlpack/core/tree/binary_space_tree/dual_tree_traverser.hpp
copy to src/mlpack/core/tree/spill_tree/dual_tree_traverser.hpp
index 25c9e64..80ec452 100644
--- a/src/mlpack/core/tree/binary_space_tree/dual_tree_traverser.hpp
+++ b/src/mlpack/core/tree/spill_tree/dual_tree_traverser.hpp
@@ -1,18 +1,19 @@
/**
* @file dual_tree_traverser.hpp
* @author Ryan Curtin
+ * @author Marcos Pividori
*
- * Defines the DualTreeTraverser for the BinarySpaceTree tree type. This is a
- * nested class of BinarySpaceTree which traverses two trees in a depth-first
+ * Defines the DualTreeTraverser 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.
*/
-#ifndef MLPACK_CORE_TREE_BINARY_SPACE_TREE_DUAL_TREE_TRAVERSER_HPP
-#define MLPACK_CORE_TREE_BINARY_SPACE_TREE_DUAL_TREE_TRAVERSER_HPP
+#ifndef MLPACK_CORE_TREE_SPILL_TREE_DUAL_TREE_TRAVERSER_HPP
+#define MLPACK_CORE_TREE_SPILL_TREE_DUAL_TREE_TRAVERSER_HPP
#include <mlpack/core.hpp>
-#include "binary_space_tree.hpp"
+#include "spill_tree.hpp"
namespace mlpack {
namespace tree {
@@ -24,7 +25,7 @@ template<typename MetricType,
template<typename SplitBoundType, typename SplitMatType>
class SplitType>
template<typename RuleType>
-class BinarySpaceTree<MetricType, StatisticType, MatType, BoundType,
+class SpillTree<MetricType, StatisticType, MatType, BoundType,
SplitType>::DualTreeTraverser
{
public:
@@ -40,8 +41,8 @@ class BinarySpaceTree<MetricType, StatisticType, MatType, BoundType,
* @param referenceNode The reference node to be traversed.
* @param score The score of the current node combination.
*/
- void Traverse(BinarySpaceTree& queryNode,
- BinarySpaceTree& referenceNode);
+ void Traverse(SpillTree& queryNode,
+ SpillTree& referenceNode);
//! Get the number of prunes.
size_t NumPrunes() const { return numPrunes; }
@@ -90,5 +91,5 @@ class BinarySpaceTree<MetricType, StatisticType, MatType, BoundType,
// Include implementation.
#include "dual_tree_traverser_impl.hpp"
-#endif // MLPACK_CORE_TREE_BINARY_SPACE_TREE_DUAL_TREE_TRAVERSER_HPP
+#endif // MLPACK_CORE_TREE_SPILL_TREE_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/dual_tree_traverser_impl.hpp
new file mode 100644
index 0000000..f47dc4a
--- /dev/null
+++ b/src/mlpack/core/tree/spill_tree/dual_tree_traverser_impl.hpp
@@ -0,0 +1,57 @@
+/**
+ * @file dual_tree_traverser_impl.hpp
+ * @author Ryan Curtin
+ * @author Marcos Pividori
+ *
+ * Implementation of the DualTreeTraverser 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
+
+// In case it hasn't been included yet.
+#include "dual_tree_traverser.hpp"
+
+namespace mlpack {
+namespace tree {
+
+template<typename MetricType,
+ typename StatisticType,
+ typename MatType,
+ template<typename BoundMetricType, typename...> class BoundType,
+ template<typename SplitBoundType, typename SplitMatType>
+ class SplitType>
+template<typename RuleType>
+SpillTree<MetricType, StatisticType, MatType, BoundType, SplitType>::
+DualTreeTraverser<RuleType>::DualTreeTraverser(RuleType& rule) :
+ rule(rule),
+ numPrunes(0),
+ numVisited(0),
+ numScores(0),
+ numBaseCases(0)
+{ /* Nothing to do. */ }
+
+template<typename MetricType,
+ typename StatisticType,
+ typename MatType,
+ template<typename BoundMetricType, typename...> class BoundType,
+ template<typename SplitBoundType, typename SplitMatType>
+ class SplitType>
+template<typename RuleType>
+void SpillTree<MetricType, StatisticType, MatType, BoundType, SplitType>::
+DualTreeTraverser<RuleType>::Traverse(
+ SpillTree<MetricType, StatisticType, MatType, BoundType, SplitType>&
+ /* queryNode */,
+ SpillTree<MetricType, StatisticType, MatType, BoundType, SplitType>&
+ /* referenceNode */)
+{
+ // TODO: Add support for dual tree traverser.
+ throw std::runtime_error("Dual tree traverser not implemented for "
+ "spill trees.");
+}
+
+} // namespace tree
+} // namespace mlpack
+
+#endif // MLPACK_CORE_TREE_SPILL_TREE_DUAL_TREE_TRAVERSER_IMPL_HPP
diff --git a/src/mlpack/core/tree/binary_space_tree/single_tree_traverser.hpp b/src/mlpack/core/tree/spill_tree/single_tree_traverser.hpp
similarity index 71%
copy from src/mlpack/core/tree/binary_space_tree/single_tree_traverser.hpp
copy to src/mlpack/core/tree/spill_tree/single_tree_traverser.hpp
index caa3d97..fe0e842 100644
--- a/src/mlpack/core/tree/binary_space_tree/single_tree_traverser.hpp
+++ b/src/mlpack/core/tree/spill_tree/single_tree_traverser.hpp
@@ -1,17 +1,20 @@
/**
* @file single_tree_traverser.hpp
* @author Ryan Curtin
+ * @author Marcos Pividori
*
- * A nested class of BinarySpaceTree which traverses the entire tree with a
+ * 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.
+ * order in which to recurse. This traverser implements a Hybrid sp-tree
+ * depth-first search. Does defeatist search on overlapping nodes,
+ * and backtracking on non-overlapping nodes.
*/
-#ifndef MLPACK_CORE_TREE_BINARY_SPACE_TREE_SINGLE_TREE_TRAVERSER_HPP
-#define MLPACK_CORE_TREE_BINARY_SPACE_TREE_SINGLE_TREE_TRAVERSER_HPP
+#ifndef MLPACK_CORE_TREE_SPILL_TREE_SINGLE_TREE_TRAVERSER_HPP
+#define MLPACK_CORE_TREE_SPILL_TREE_SINGLE_TREE_TRAVERSER_HPP
#include <mlpack/core.hpp>
-#include "binary_space_tree.hpp"
+#include "spill_tree.hpp"
namespace mlpack {
namespace tree {
@@ -23,7 +26,7 @@ template<typename MetricType,
template<typename SplitBoundType, typename SplitMatType>
class SplitType>
template<typename RuleType>
-class BinarySpaceTree<MetricType, StatisticType, MatType, BoundType,
+class SpillTree<MetricType, StatisticType, MatType, BoundType,
SplitType>::SingleTreeTraverser
{
public:
@@ -39,7 +42,7 @@ class BinarySpaceTree<MetricType, StatisticType, MatType, BoundType,
* used as the query point.
* @param referenceNode The tree node to be traversed.
*/
- void Traverse(const size_t queryIndex, BinarySpaceTree& referenceNode);
+ void Traverse(const size_t queryIndex, SpillTree& referenceNode);
//! Get the number of prunes.
size_t NumPrunes() const { return numPrunes; }
diff --git a/src/mlpack/core/tree/binary_space_tree/single_tree_traverser_impl.hpp b/src/mlpack/core/tree/spill_tree/single_tree_traverser_impl.hpp
similarity index 68%
copy from src/mlpack/core/tree/binary_space_tree/single_tree_traverser_impl.hpp
copy to src/mlpack/core/tree/spill_tree/single_tree_traverser_impl.hpp
index c9f6b1e..4bfb9fc 100644
--- a/src/mlpack/core/tree/binary_space_tree/single_tree_traverser_impl.hpp
+++ b/src/mlpack/core/tree/spill_tree/single_tree_traverser_impl.hpp
@@ -1,19 +1,20 @@
/**
* @file single_tree_traverser_impl.hpp
* @author Ryan Curtin
+ * @author Marcos Pividori
*
- * A nested class of BinarySpaceTree which traverses the entire tree with a
+ * 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.
+ * order in which to recurse. This traverser implements a Hybrid sp-tree
+ * depth-first search. Does defeatist search on overlapping nodes,
+ * and backtracking on non-overlapping nodes.
*/
-#ifndef MLPACK_CORE_TREE_BINARY_SPACE_TREE_SINGLE_TREE_TRAVERSER_IMPL_HPP
-#define MLPACK_CORE_TREE_BINARY_SPACE_TREE_SINGLE_TREE_TRAVERSER_IMPL_HPP
+#ifndef MLPACK_CORE_TREE_SPILL_TREE_SINGLE_TREE_TRAVERSER_IMPL_HPP
+#define MLPACK_CORE_TREE_SPILL_TREE_SINGLE_TREE_TRAVERSER_IMPL_HPP
// In case it hasn't been included yet.
#include "single_tree_traverser.hpp"
-#include <stack>
-
namespace mlpack {
namespace tree {
@@ -24,7 +25,7 @@ template<typename MetricType,
template<typename SplitBoundType, typename SplitMatType>
class SplitType>
template<typename RuleType>
-BinarySpaceTree<MetricType, StatisticType, MatType, BoundType, SplitType>::
+SpillTree<MetricType, StatisticType, MatType, BoundType, SplitType>::
SingleTreeTraverser<RuleType>::SingleTreeTraverser(RuleType& rule) :
rule(rule),
numPrunes(0)
@@ -37,18 +38,17 @@ template<typename MetricType,
template<typename SplitBoundType, typename SplitMatType>
class SplitType>
template<typename RuleType>
-void BinarySpaceTree<MetricType, StatisticType, MatType, BoundType, SplitType>::
+void SpillTree<MetricType, StatisticType, MatType, BoundType, SplitType>::
SingleTreeTraverser<RuleType>::Traverse(
const size_t queryIndex,
- BinarySpaceTree<MetricType, StatisticType, MatType, BoundType, SplitType>&
+ SpillTree<MetricType, StatisticType, MatType, BoundType, SplitType>&
referenceNode)
{
// If we are a leaf, run the base case as necessary.
if (referenceNode.IsLeaf())
{
- const size_t refEnd = referenceNode.Begin() + referenceNode.Count();
- for (size_t i = referenceNode.Begin(); i < refEnd; ++i)
- rule.BaseCase(queryIndex, i);
+ for (size_t i = 0; i < referenceNode.NumPoints(); ++i)
+ rule.BaseCase(queryIndex, referenceNode.Point(i));
}
else
{
@@ -61,6 +61,13 @@ SingleTreeTraverser<RuleType>::Traverse(
// Recurse to the left.
Traverse(queryIndex, *referenceNode.Left());
+ // If overlapping node, let's do defeatist search and ignore backtracking.
+ if (referenceNode.Overlap())
+ {
+ ++numPrunes;
+ return;
+ }
+
// Is it still valid to recurse to the right?
rightScore = rule.Rescore(queryIndex, *referenceNode.Right(), rightScore);
@@ -74,6 +81,13 @@ SingleTreeTraverser<RuleType>::Traverse(
// Recurse to the right.
Traverse(queryIndex, *referenceNode.Right());
+ // If overlapping node, let's do defeatist search and ignore backtracking.
+ if (referenceNode.Overlap())
+ {
+ ++numPrunes;
+ return;
+ }
+
// Is it still valid to recurse to the left?
leftScore = rule.Rescore(queryIndex, *referenceNode.Left(), leftScore);
@@ -93,6 +107,14 @@ SingleTreeTraverser<RuleType>::Traverse(
// Choose the left first.
Traverse(queryIndex, *referenceNode.Left());
+ // If overlapping node, let's do defeatist search and ignore
+ // backtracking.
+ if (referenceNode.Overlap())
+ {
+ ++numPrunes;
+ return;
+ }
+
// Is it still valid to recurse to the right?
rightScore = rule.Rescore(queryIndex, *referenceNode.Right(),
rightScore);
diff --git a/src/mlpack/core/tree/spill_tree/spill_tree.hpp b/src/mlpack/core/tree/spill_tree/spill_tree.hpp
index db7f6c0..e563b49 100644
--- a/src/mlpack/core/tree/spill_tree/spill_tree.hpp
+++ b/src/mlpack/core/tree/spill_tree/spill_tree.hpp
@@ -116,9 +116,6 @@ class SpillTree
template<typename RuleType>
class DualTreeTraverser;
- template<typename RuleType>
- class BreadthFirstDualTreeTraverser;
-
/**
* Construct this as the root node of a hybrid spill tree using the given
* dataset. This will copy the input matrix; if you don't want this, consider
@@ -236,6 +233,9 @@ class SpillTree
//! Modify the dataset which the tree is built on. Be careful!
MatType& Dataset() { return *dataset; }
+ //! Distinguish overlapping nodes from non-overlapping nodes.
+ bool Overlap() const { return overlappingNode; }
+
//! Get the metric that the tree uses.
MetricType Metric() const { return MetricType(); }
More information about the mlpack-git
mailing list