mlpack 3.4.2
rectangle_tree.hpp
Go to the documentation of this file.
1
13#ifndef MLPACK_CORE_TREE_RECTANGLE_TREE_RECTANGLE_TREE_HPP
14#define MLPACK_CORE_TREE_RECTANGLE_TREE_RECTANGLE_TREE_HPP
15
16#include <mlpack/prereqs.hpp>
17
18#include "../hrectbound.hpp"
19#include "../statistic.hpp"
20#include "r_tree_split.hpp"
23
24namespace mlpack {
25namespace tree {
26
47template<typename MetricType = metric::EuclideanDistance,
48 typename StatisticType = EmptyStatistic,
49 typename MatType = arma::mat,
50 typename SplitType = RTreeSplit,
51 typename DescentType = RTreeDescentHeuristic,
52 template<typename> class AuxiliaryInformationType =
53 NoAuxiliaryInformation>
55{
56 // The metric *must* be the euclidean distance.
57 static_assert(boost::is_same<MetricType, metric::EuclideanDistance>::value,
58 "RectangleTree: MetricType must be metric::EuclideanDistance.");
59
60 public:
62 typedef MatType Mat;
64 typedef typename MatType::elem_type ElemType;
66 typedef AuxiliaryInformationType<RectangleTree> AuxiliaryInformation;
67 private:
69 size_t maxNumChildren;
71 size_t minNumChildren;
73 size_t numChildren;
75 std::vector<RectangleTree*> children;
77 RectangleTree* parent;
82 size_t begin;
85 size_t count;
87 size_t numDescendants;
89 size_t maxLeafSize;
91 size_t minLeafSize;
95 StatisticType stat;
97 ElemType parentDistance;
99 const MatType* dataset;
102 bool ownsDataset;
104 std::vector<size_t> points;
106 AuxiliaryInformationType<RectangleTree> auxiliaryInfo;
107
108 public:
111 template<typename RuleType>
114 template<typename RuleType>
115 class DualTreeTraverser;
116
131 RectangleTree(const MatType& data,
132 const size_t maxLeafSize = 20,
133 const size_t minLeafSize = 8,
134 const size_t maxNumChildren = 5,
135 const size_t minNumChildren = 2,
136 const size_t firstDataIndex = 0);
137
152 RectangleTree(MatType&& data,
153 const size_t maxLeafSize = 20,
154 const size_t minLeafSize = 8,
155 const size_t maxNumChildren = 5,
156 const size_t minNumChildren = 2,
157 const size_t firstDataIndex = 0);
158
167 explicit RectangleTree(RectangleTree* parentNode,
168 const size_t numMaxChildren = 0);
169
179 const bool deepCopy = true,
180 RectangleTree* newParent = NULL);
181
188
195
202
206 template<typename Archive>
208 Archive& ar,
210
217
224
230
236 void InsertPoint(const size_t point);
237
246 void InsertPoint(const size_t point, std::vector<bool>& relevels);
247
260 const size_t level,
261 std::vector<bool>& relevels);
262
270 bool DeletePoint(const size_t point);
271
280 bool DeletePoint(const size_t point, std::vector<bool>& relevels);
281
286 bool RemoveNode(const RectangleTree* node, std::vector<bool>& relevels);
287
299 const RectangleTree* FindByBeginCount(size_t begin, size_t count) const;
300
312 RectangleTree* FindByBeginCount(size_t begin, size_t count);
313
315 const bound::HRectBound<MetricType>& Bound() const { return bound; }
318
320 const StatisticType& Stat() const { return stat; }
322 StatisticType& Stat() { return stat; }
323
325 const AuxiliaryInformationType<RectangleTree> &AuxiliaryInfo() const
326 { return auxiliaryInfo; }
328 AuxiliaryInformationType<RectangleTree>& AuxiliaryInfo()
329 { return auxiliaryInfo; }
330
332 bool IsLeaf() const;
333
335 size_t MaxLeafSize() const { return maxLeafSize; }
337 size_t& MaxLeafSize() { return maxLeafSize; }
338
340 size_t MinLeafSize() const { return minLeafSize; }
342 size_t& MinLeafSize() { return minLeafSize; }
343
345 size_t MaxNumChildren() const { return maxNumChildren; }
347 size_t& MaxNumChildren() { return maxNumChildren; }
348
350 size_t MinNumChildren() const { return minNumChildren; }
352 size_t& MinNumChildren() { return minNumChildren; }
353
355 RectangleTree* Parent() const { return parent; }
357 RectangleTree*& Parent() { return parent; }
358
360 const MatType& Dataset() const { return *dataset; }
362 MatType& Dataset() { return const_cast<MatType&>(*dataset); }
363
365 MetricType Metric() const { return MetricType(); }
366
368 void Center(arma::vec& center) { bound.Center(center); }
369
371 size_t NumChildren() const { return numChildren; }
373 size_t& NumChildren() { return numChildren; }
374
379 template<typename VecType>
381 const VecType& point,
383
388 template<typename VecType>
390 const VecType& point,
392
397 size_t GetNearestChild(const RectangleTree& queryNode);
398
403 size_t GetFurthestChild(const RectangleTree& queryNode);
404
410
419
423 ElemType MinimumBoundDistance() const { return bound.MinWidth() / 2.0; }
424
427 ElemType ParentDistance() const { return parentDistance; }
430 ElemType& ParentDistance() { return parentDistance; }
431
437 inline RectangleTree& Child(const size_t child) const
438 {
439 return *children[child];
440 }
441
447 inline RectangleTree& Child(const size_t child)
448 {
449 return *children[child];
450 }
451
454 size_t NumPoints() const;
455
461 size_t NumDescendants() const;
462
470 size_t Descendant(const size_t index) const;
471
480 size_t Point(const size_t index) const { return points[index]; }
481
484 size_t& Point(const size_t index) { return points[index]; }
485
488 {
489 return bound.MinDistance(other.Bound());
490 }
491
494 {
495 return bound.MaxDistance(other.Bound());
496 }
497
500 {
501 return bound.RangeDistance(other.Bound());
502 }
503
505 template<typename VecType>
506 ElemType MinDistance(const VecType& point,
508 const
509 {
510 return bound.MinDistance(point);
511 }
512
514 template<typename VecType>
515 ElemType MaxDistance(const VecType& point,
517 const
518 {
519 return bound.MaxDistance(point);
520 }
521
523 template<typename VecType>
525 const VecType& point,
526 typename std::enable_if_t<IsVector<VecType>::value>* = 0) const
527 {
528 return bound.RangeDistance(point);
529 }
530
534 size_t TreeSize() const;
535
540 size_t TreeDepth() const;
541
543 size_t Begin() const { return begin; }
545 size_t& Begin() { return begin; }
546
548 size_t Count() const { return count; }
550 size_t& Count() { return count; }
551
552 private:
558 void SplitNode(std::vector<bool>& relevels);
559
565 void BuildStatistics(RectangleTree* node);
566
567 protected:
575
577 friend class boost::serialization::access;
578
581
583 friend SplitType;
584
587
588 public:
602 void CondenseTree(const arma::vec& point,
603 std::vector<bool>& relevels,
604 const bool usePoint);
605
613 bool ShrinkBoundForPoint(const arma::vec& point);
614
623
628
632 template<typename Archive>
633 void serialize(Archive& ar, const unsigned int /* version */);
634};
635
636} // namespace tree
637} // namespace mlpack
638
639// Include implementation.
640#include "rectangle_tree_impl.hpp"
641
642#endif
ElemType MinDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Calculates minimum bound-to-point distance.
ElemType MinWidth() const
Get the minimum width of the bound.
Definition: hrectbound.hpp:102
void Center(arma::Col< ElemType > &center) const
Calculates the center of the range, placing it into the given vector.
math::RangeType< ElemType > RangeDistance(const HRectBound &other) const
Calculates minimum and maximum bound-to-bound distance.
ElemType MaxDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Calculates maximum bound-to-point squared distance.
Simple real-valued range.
Definition: range.hpp:35
A dual tree traverser for rectangle type trees.
A single traverser for rectangle type trees.
A rectangle type tree tree, such as an R-tree or X-tree.
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.
bool DeletePoint(const size_t point)
Deletes a point from the treeand, updates the bounding rectangle.
bool DeletePoint(const size_t point, std::vector< bool > &relevels)
Deletes a point from the tree, updates the bounding rectangle, tracking levels.
RectangleTree * Parent() const
Gets the parent of this node.
ElemType MinDistance(const RectangleTree &other) const
Return the minimum distance to another node.
RectangleTree(const MatType &data, const size_t maxLeafSize=20, const size_t minLeafSize=8, const size_t maxNumChildren=5, const size_t minNumChildren=2, const size_t firstDataIndex=0)
Construct this as the root node of a rectangle type tree using the given dataset.
bool ShrinkBoundForPoint(const arma::vec &point)
Shrink the bound object of this node for the removal of a point.
void Center(arma::vec &center)
Get the centroid of the node and store it 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.
size_t NumChildren() const
Return the number of child nodes. (One level beneath this one only.)
ElemType MinimumBoundDistance() const
Return the minimum distance from the center to any edge of the bound.
MatType::elem_type ElemType
The element type held by the matrix type.
size_t & MaxNumChildren()
Modify the maximum number of children (in a non-leaf node).
size_t MaxNumChildren() const
Return the maximum number of children (in a non-leaf node).
ElemType & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
size_t & MinNumChildren()
Modify the minimum number of children (in a non-leaf node).
size_t NumDescendants() const
Return the number of descendants of this node.
MatType & Dataset()
Modify the dataset which the tree is built on. Be careful!
RectangleTree(Archive &ar, const typename std::enable_if_t< Archive::is_loading::value > *=0)
Construct the tree from a boost::serialization archive.
void InsertPoint(const size_t point)
Inserts a point into the tree.
size_t MaxLeafSize() const
Return the maximum leaf size.
RectangleTree(RectangleTree &&other)
Create a rectangle tree by moving the other tree.
size_t & MaxLeafSize()
Modify the maximum leaf size.
size_t NumPoints() const
Return the number of points in this node (returns 0 if this node is not a leaf).
void InsertNode(RectangleTree *node, const size_t level, std::vector< bool > &relevels)
Inserts a node into the tree, tracking which levels have been inserted into.
size_t & Begin()
Modify the index of the beginning point of this subset.
RectangleTree * FindByBeginCount(size_t begin, size_t count)
Find a node in this tree by its begin and count.
RectangleTree(RectangleTree *parentNode, const size_t numMaxChildren=0)
Construct this as an empty node with the specified parent.
StatisticType & Stat()
Modify the statistic object for this node.
size_t & MinLeafSize()
Modify the minimum leaf size.
AuxiliaryInformationType< RectangleTree > AuxiliaryInformation
The auxiliary information type held by the tree.
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.
RectangleTree * ExactClone()
Make an exact copy of this node, pointers and everything.
size_t MinNumChildren() const
Return the minimum number of children (in a non-leaf node).
size_t TreeDepth() const
Obtains the number of levels below this node in the tree, starting with this.
const RectangleTree * FindByBeginCount(size_t begin, size_t count) const
Find a node in this tree by its begin and count (const).
RectangleTree(const RectangleTree &other, const bool deepCopy=true, RectangleTree *newParent=NULL)
Create a rectangle tree by copying the other tree.
~RectangleTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn.
ElemType MinDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Return the minimum distance to another point.
size_t & Point(const size_t index)
Modify the index of a particular point in this node.
void NullifyData()
Nullify the auxiliary information.
RectangleTree()
A default constructor.
bool RemoveNode(const RectangleTree *node, std::vector< bool > &relevels)
Removes a node from the tree.
RectangleTree & Child(const size_t child)
Modify the specified child.
RectangleTree & operator=(const RectangleTree &other)
Copy the given rectangle tree.
ElemType MaxDistance(const RectangleTree &other) const
Return the maximum distance to another node.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
void InsertPoint(const size_t point, std::vector< bool > &relevels)
Inserts a point into the tree, tracking which levels have been inserted into.
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant of this node.
const StatisticType & Stat() const
Return the statistic object for this node.
size_t & Count()
Modify the number of points in this subset.
RectangleTree *& Parent()
Modify the parent of this node.
const bound::HRectBound< MetricType > & Bound() const
Return the bound object for this node.
size_t Count() const
Return the number of points in this subset.
size_t & NumChildren()
Modify the number of child nodes. Be careful.
MetricType Metric() const
Get the metric which the tree uses.
size_t TreeSize() const
Obtains the number of nodes in the tree, starting with this.
bool ShrinkBoundForBound(const bound::HRectBound< MetricType > &changedBound)
Shrink the bound object of this node for the removal of a child node.
RectangleTree & operator=(RectangleTree &&other)
Take ownership of the given rectangle tree.
friend AuxiliaryInformation
Give friend access for AuxiliaryInformationType.
size_t Begin() const
Return the index of the beginning point of this subset.
RectangleTree & Child(const size_t child) const
Get the specified child.
ElemType FurthestPointDistance() const
Return the furthest distance to a point held in this node.
friend DescentType
Give friend access for DescentType.
void SoftDelete()
Delete this node of the tree, but leave the stuff contained in it intact.
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.
size_t GetNearestChild(const RectangleTree &queryNode)
Return the index of the nearest child node to the given query node.
const MatType & Dataset() const
Get the dataset which the tree is built on.
ElemType FurthestDescendantDistance() const
Return the furthest possible descendant distance.
size_t MinLeafSize() const
Return the minimum leaf size.
math::RangeType< ElemType > RangeDistance(const RectangleTree &other) const
Return the minimum and maximum distance to another node.
void CondenseTree(const arma::vec &point, std::vector< bool > &relevels, const bool usePoint)
Condense the bounding rectangles for this node based on the removal of the point specified by the arm...
ElemType MaxDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Return the maximum distance to another point.
size_t GetFurthestChild(const RectangleTree &queryNode)
Return the index of the furthest child node to the given query node.
const AuxiliaryInformationType< RectangleTree > & AuxiliaryInfo() const
Return the auxiliary information object of this node.
AuxiliaryInformationType< RectangleTree > & AuxiliaryInfo()
Modify the split object of this node.
void serialize(Archive &ar, const unsigned int)
Serialize the tree.
RectangleTree(MatType &&data, const size_t maxLeafSize=20, const size_t minLeafSize=8, const size_t maxNumChildren=5, const size_t minNumChildren=2, const size_t firstDataIndex=0)
Construct this as the root node of a rectangle tree type using the given dataset, and taking ownershi...
bound::HRectBound< MetricType > & Bound()
Modify the bound object for this node.
ElemType ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
friend SplitType
Give friend access for SplitType.
LMetric< 2, true > EuclideanDistance
The Euclidean (L2) distance.
Definition: lmetric.hpp:112
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: cv.hpp:1
typename enable_if< B, T >::type enable_if_t
Definition: prereqs.hpp:70
The core includes that mlpack expects; standard C++ includes and Armadillo.
If value == true, then VecType is some sort of Armadillo vector or subview.
Definition: arma_traits.hpp:36