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 
24 namespace mlpack {
25 namespace tree {
26 
47 template<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(std::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 
178  RectangleTree(const RectangleTree& other,
179  const bool deepCopy = true,
180  RectangleTree* newParent = NULL);
181 
187  RectangleTree(RectangleTree&& other);
188 
194  RectangleTree& operator=(const RectangleTree& other);
195 
202 
206  template<typename Archive>
208  Archive& ar,
209  const typename std::enable_if_t<cereal::is_loading<Archive>()>* = 0);
210 
216  ~RectangleTree();
217 
223  void SoftDelete();
224 
229  void NullifyData();
230 
236  void InsertPoint(const size_t point);
237 
246  void InsertPoint(const size_t point, std::vector<bool>& relevels);
247 
259  void InsertNode(RectangleTree* node,
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>
380  size_t GetNearestChild(
381  const VecType& point,
383 
388  template<typename VecType>
389  size_t GetFurthestChild(
390  const VecType& point,
392 
397  size_t GetNearestChild(const RectangleTree& queryNode);
398 
403  size_t GetFurthestChild(const RectangleTree& queryNode);
404 
409  ElemType FurthestPointDistance() const;
410 
418  ElemType FurthestDescendantDistance() const;
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 
487  ElemType MinDistance(const RectangleTree& other) const
488  {
489  return bound.MinDistance(other.Bound());
490  }
491 
493  ElemType MaxDistance(const RectangleTree& other) const
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:
574  RectangleTree();
575 
577  friend class cereal::access;
578 
580  friend DescentType;
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 
622  bool ShrinkBoundForBound(const bound::HRectBound<MetricType>& changedBound);
623 
628 
632  template<typename Archive>
633  void serialize(Archive& ar, const uint32_t /* version */);
634 };
635 
636 } // namespace tree
637 } // namespace mlpack
638 
639 // Include implementation.
640 #include "rectangle_tree_impl.hpp"
641 
642 #endif
MatType Mat
So other classes can use TreeType::Mat.
size_t & Count()
Modify the number of points in this subset.
RectangleTree *& Parent()
Modify the parent of this node.
const AuxiliaryInformationType< RectangleTree > & AuxiliaryInfo() const
Return the auxiliary information object of this node.
bool ShrinkBoundForPoint(const arma::vec &point)
Shrink the bound object of this node for the removal of a point.
typename enable_if< B, T >::type enable_if_t
Definition: prereqs.hpp:70
ElemType & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
Linear algebra utility functions, generally performed on matrices or vectors.
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant of this node...
ElemType MaxDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Return the maximum distance to another point.
const MatType & Dataset() const
Get the dataset which the tree is built on.
math::RangeType< ElemType > RangeDistance(const HRectBound &other) const
Calculates minimum and maximum bound-to-bound distance.
The core includes that mlpack expects; standard C++ includes and Armadillo.
RectangleTree & Child(const size_t child) const
Get the specified child.
ElemType MaxDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Calculates maximum bound-to-point squared distance.
size_t TreeSize() const
Obtains the number of nodes in the tree, starting with this.
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.
ElemType FurthestPointDistance() const
Return the furthest distance to a point held in this node.
AuxiliaryInformationType< RectangleTree > AuxiliaryInformation
The auxiliary information type held by the tree.
size_t & MaxNumChildren()
Modify the maximum number of children (in a non-leaf node).
friend DescentType
Give friend access for DescentType.
size_t & Begin()
Modify the index of the beginning point of this subset.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
ElemType MinWidth() const
Get the minimum width of the bound.
Definition: hrectbound.hpp:106
const bound::HRectBound< MetricType > & Bound() const
Return the bound object for this node.
MetricType Metric() const
Get the metric which the tree uses.
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...
void SoftDelete()
Delete this node of the tree, but leave the stuff contained in it intact.
size_t MinNumChildren() const
Return the minimum number of children (in a non-leaf node).
size_t MaxNumChildren() const
Return the maximum number of children (in a non-leaf node).
ElemType MinDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Calculates minimum bound-to-point distance.
size_t NumDescendants() const
Return the number of descendants of this node.
size_t & MinLeafSize()
Modify the minimum leaf size.
constexpr auto data(Container const &container) noexcept -> decltype(container.data())
Definition: iterator.hpp:79
size_t NumChildren() const
Return the number of child nodes. (One level beneath this one only.)
ElemType MinDistance(const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
Return the minimum distance to another point.
size_t Begin() const
Return the index of the beginning point of this subset.
ElemType FurthestDescendantDistance() const
Return the furthest possible descendant distance.
A rectangle type tree tree, such as an R-tree or X-tree.
const StatisticType & Stat() const
Return the statistic object for this node.
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
StatisticType & Stat()
Modify the statistic object for this node.
void InsertPoint(const size_t point)
Inserts a point into the tree.
ElemType MaxDistance(const RectangleTree &other) const
Return the maximum distance to another node.
A dual tree traverser for rectangle type trees.
~RectangleTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn...
bool RemoveNode(const RectangleTree *node, std::vector< bool > &relevels)
Removes a node from the tree.
size_t & MaxLeafSize()
Modify the maximum leaf size.
friend AuxiliaryInformation
Give friend access for AuxiliaryInformationType.
void NullifyData()
Nullify the auxiliary information.
size_t Count() const
Return the number of points in this subset.
const RectangleTree * FindByBeginCount(size_t begin, size_t count) const
Find a node in this tree by its begin and count (const).
bool DeletePoint(const size_t point)
Deletes a point from the treeand, updates the bounding rectangle.
void Center(arma::vec &center)
Get the centroid of the node and store it in the given vector.
RectangleTree & operator=(const RectangleTree &other)
Copy the given rectangle tree.
size_t TreeDepth() const
Obtains the number of levels below this node in the tree, starting with this.
size_t NumPoints() const
Return the number of points in this node (returns 0 if this node is not a leaf).
MatType::elem_type ElemType
The element type held by the matrix type.
size_t & NumChildren()
Modify the number of child nodes. Be careful.
size_t MinLeafSize() const
Return the minimum leaf size.
auto count(Range &&rng, T const &value) -> enable_if_t< is_range< Range >::value, decltype(::std::count(::std::begin(::core::forward< Range >(rng)), ::std::end(::core::forward< Range >(rng)), value)) >
Definition: algorithm.hpp:225
A single traverser for rectangle type trees.
AuxiliaryInformationType< RectangleTree > & AuxiliaryInfo()
Modify the split object of this node.
MatType & Dataset()
Modify the dataset which the tree is built on. Be careful!
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.
friend SplitType
Give friend access for SplitType.
size_t & Point(const size_t index)
Modify the index of a particular point in this node.
ElemType MinDistance(const RectangleTree &other) const
Return the minimum distance to another node.
void Center(arma::Col< ElemType > &center) const
Calculates the center of the range, placing it into the given vector.
RectangleTree & Child(const size_t child)
Modify the specified child.
LMetric< 2, true > EuclideanDistance
The Euclidean (L2) distance.
Definition: lmetric.hpp:112
math::RangeType< ElemType > RangeDistance(const RectangleTree &other) const
Return the minimum and maximum distance to another node.
size_t & MinNumChildren()
Modify the minimum number of children (in a non-leaf node).
RectangleTree * Parent() const
Gets the parent of this node.
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.
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.
bound::HRectBound< MetricType > & Bound()
Modify the bound object for this node.
ElemType MinimumBoundDistance() const
Return the minimum distance from the center to any edge of the bound.
ElemType ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
If value == true, then VecType is some sort of Armadillo vector or subview.
Definition: arma_traits.hpp:35
bool ShrinkBoundForBound(const bound::HRectBound< MetricType > &changedBound)
Shrink the bound object of this node for the removal of a child node.
RectangleTree()
A default constructor.
RectangleTree * ExactClone()
Make an exact copy of this node, pointers and everything.
size_t MaxLeafSize() const
Return the maximum leaf size.
void serialize(Archive &ar, const uint32_t)
Serialize the tree.