11#ifndef MLPACK_CORE_TREE_SPILL_TREE_SPILL_TREE_HPP
12#define MLPACK_CORE_TREE_SPILL_TREE_SPILL_TREE_HPP
15#include "../space_split/midpoint_space_split.hpp"
16#include "../statistic.hpp"
66template<
typename MetricType,
67 typename StatisticType = EmptyStatistic,
68 typename MatType = arma::mat,
69 template<
typename HyperplaneMetricType>
71 template<
typename SplitMetricType,
typename SplitMatType>
72 class SplitType = MidpointSpaceSplit>
81 typedef typename HyperplaneType<MetricType>::BoundType
BoundType;
95 arma::Col<size_t>* pointsIndex;
99 HyperplaneType<MetricType> hyperplane;
108 ElemType furthestDescendantDistance;
113 const MatType* dataset;
121 template<
typename RuleType,
bool Defeatist = false>
128 template<
typename RuleType,
bool Defeatist = false>
133 template<
typename RuleType>
137 template<
typename RuleType>
141 template<
typename RuleType>
145 template<
typename RuleType>
159 const double tau = 0,
160 const size_t maxLeafSize = 20,
161 const double rho = 0.7);
175 const double tau = 0,
176 const size_t maxLeafSize = 20,
177 const double rho = 0.7);
191 arma::Col<size_t>& points,
192 const double tau = 0,
193 const size_t maxLeafSize = 20,
194 const double rho = 0.7);
231 template<
typename Archive>
249 const StatisticType&
Stat()
const {
return stat; }
251 StatisticType&
Stat() {
return stat; }
272 const MatType&
Dataset()
const {
return *dataset; }
275 bool Overlap()
const {
return overlappingNode; }
278 const HyperplaneType<MetricType>&
Hyperplane()
const {
return hyperplane; }
281 MetricType
Metric()
const {
return MetricType(); }
292 template<
typename VecType>
294 const VecType& point,
303 template<
typename VecType>
305 const VecType& point,
358 {
return (child == 0) ? left : right; }
387 size_t Point(
const size_t index)
const;
392 return bound.MinDistance(other.
Bound());
398 return bound.MaxDistance(other.
Bound());
404 return bound.RangeDistance(other.
Bound());
408 template<
typename VecType>
413 return bound.MinDistance(point);
417 template<
typename VecType>
422 return bound.MaxDistance(point);
426 template<
typename VecType>
431 return bound.RangeDistance(point);
438 void Center(arma::vec& center) { bound.Center(center); }
449 void SplitNode(arma::Col<size_t>& points,
450 const size_t maxLeafSize,
464 bool SplitPoints(
const double tau,
466 const arma::Col<size_t>& points,
467 arma::Col<size_t>& leftPoints,
468 arma::Col<size_t>& rightPoints);
479 friend class boost::serialization::access;
485 template<
typename Archive>
486 void serialize(Archive& ar,
const unsigned int version);
493#include "spill_tree_impl.hpp"
496#include "../spill_tree.hpp"
Simple real-valued range.
A generic dual-tree traverser for hybrid spill trees; see spill_dual_tree_traverser....
A generic single-tree traverser for hybrid spill trees; see spill_single_tree_traverser....
A hybrid spill tree is a variant of binary space trees in which the children of a node can "spill ove...
size_t GetFurthestChild(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0)
Return the index of the furthest child node to the given query point (this is an efficient estimation...
SpillTree(SpillTree &&other)
Move constructor for a SpillTree; possess all the members of the given tree.
SpillTree & operator=(SpillTree &&other)
Take ownership of the given Spill Tree.
ElemType MinDistance(const SpillTree &other) const
Return the minimum distance to another node.
size_t GetFurthestChild(const SpillTree &queryNode)
Return the index of the furthest child node to the given query node (this is an efficient estimation ...
void Center(arma::vec ¢er)
Store the center of the bounding region in the given vector.
size_t GetNearestChild(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0)
Return the index of the nearest child node to the given query point (this is an efficient estimation ...
const BoundType & Bound() const
Return the bound object for this node.
size_t NumChildren() const
Return the number of children in this node.
ElemType MinimumBoundDistance() const
Return the minimum distance from the center of the node to any bound edge.
MatType::elem_type ElemType
The type of element held in MatType.
SpillTree * Left() const
Gets the left child of this node.
ElemType & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
size_t NumDescendants() const
Return the number of descendants of this node.
size_t NumPoints() const
Return the number of points in this node (0 if not a leaf).
bool Overlap() const
Distinguish overlapping nodes from non-overlapping nodes.
StatisticType & Stat()
Return the statistic object for this node.
SpillTree * Parent() const
Gets the parent of this node.
static bool HasSelfChildren()
Returns false: this tree type does not have self children.
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
MatType Mat
So other classes can use TreeType::Mat.
SpillTree(MatType &&data, const double tau=0, const size_t maxLeafSize=20, const double rho=0.7)
Construct this as the root node of a hybrid spill tree using the given dataset.
~SpillTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn.
SpillTree(Archive &ar, const typename std::enable_if_t< Archive::is_loading::value > *=0)
Initialize the tree from a boost::serialization archive.
SpillTree *& Left()
Modify the left child of this node.
void serialize(Archive &ar, const unsigned int version)
Serialize the tree.
SpillTree & Child(const size_t child) const
Return the specified child (0 will be left, 1 will be right).
BoundType & Bound()
Return the bound object for this node.
ElemType MinDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Return the minimum distance to another point.
ElemType MaxDistance(const SpillTree &other) const
Return the maximum distance to another node.
SpillTree & operator=(const SpillTree &other)
Copy the given Spill Tree.
const HyperplaneType< MetricType > & Hyperplane() const
Get the Hyperplane instance.
SpillTree(SpillTree *parent, arma::Col< size_t > &points, const double tau=0, const size_t maxLeafSize=20, const double rho=0.7)
Construct this node as a child of the given parent, including the given list of points.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
SpillTree *& Parent()
Modify the parent of this node.
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant of this node.
SpillTree *& Right()
Modify the right child of this node.
const StatisticType & Stat() const
Return the statistic object for this node.
MetricType Metric() const
Get the metric that the tree uses.
ElemType FurthestPointDistance() const
Return the furthest distance to a point held in this node.
math::RangeType< ElemType > RangeDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Return the minimum and maximum distance to another point.
math::RangeType< ElemType > RangeDistance(const SpillTree &other) const
Return the minimum and maximum distance to another node.
SpillTree * Right() const
Gets the right child of this node.
const MatType & Dataset() const
Get the dataset which the tree is built on.
ElemType FurthestDescendantDistance() const
Return the furthest possible descendant distance.
ElemType MaxDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Return the maximum distance to another point.
size_t GetNearestChild(const SpillTree &queryNode)
Return the index of the nearest child node to the given query node (this is an efficient estimation b...
SpillTree(const MatType &data, const double tau=0, const size_t maxLeafSize=20, const double rho=0.7)
Construct this as the root node of a hybrid spill tree using the given dataset.
ElemType ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
SpillTree *& ChildPtr(const size_t child)
SpillTree()
A default constructor.
SpillTree(const SpillTree &other)
Create a hybrid spill tree by copying the other tree.
HyperplaneType< MetricType >::BoundType BoundType
The bound type.
HyperplaneBase< bound::HRectBound< MetricType >, AxisParallelProjVector > AxisOrthogonalHyperplane
AxisOrthogonalHyperplane represents a hyperplane orthogonal to an axis.
Linear algebra utility functions, generally performed on matrices or vectors.
typename enable_if< B, T >::type enable_if_t
The core includes that mlpack expects; standard C++ includes and Armadillo.
If value == true, then VecType is some sort of Armadillo vector or subview.