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(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 
177  RectangleTree(const RectangleTree& other,
178  const bool deepCopy = true,
179  RectangleTree* newParent = NULL);
180 
186  RectangleTree(RectangleTree&& other);
187 
193  RectangleTree& operator=(const RectangleTree& other);
194 
201 
205  template<typename Archive>
207  Archive& ar,
209 
215  ~RectangleTree();
216 
222  void SoftDelete();
223 
228  void NullifyData();
229 
235  void InsertPoint(const size_t point);
236 
245  void InsertPoint(const size_t point, std::vector<bool>& relevels);
246 
258  void InsertNode(RectangleTree* node,
259  const size_t level,
260  std::vector<bool>& relevels);
261 
269  bool DeletePoint(const size_t point);
270 
279  bool DeletePoint(const size_t point, std::vector<bool>& relevels);
280 
285  bool RemoveNode(const RectangleTree* node, std::vector<bool>& relevels);
286 
298  const RectangleTree* FindByBeginCount(size_t begin, size_t count) const;
299 
311  RectangleTree* FindByBeginCount(size_t begin, size_t count);
312 
314  const bound::HRectBound<MetricType>& Bound() const { return bound; }
317 
319  const StatisticType& Stat() const { return stat; }
321  StatisticType& Stat() { return stat; }
322 
324  const AuxiliaryInformationType<RectangleTree> &AuxiliaryInfo() const
325  { return auxiliaryInfo; }
327  AuxiliaryInformationType<RectangleTree>& AuxiliaryInfo()
328  { return auxiliaryInfo; }
329 
331  bool IsLeaf() const;
332 
334  size_t MaxLeafSize() const { return maxLeafSize; }
336  size_t& MaxLeafSize() { return maxLeafSize; }
337 
339  size_t MinLeafSize() const { return minLeafSize; }
341  size_t& MinLeafSize() { return minLeafSize; }
342 
344  size_t MaxNumChildren() const { return maxNumChildren; }
346  size_t& MaxNumChildren() { return maxNumChildren; }
347 
349  size_t MinNumChildren() const { return minNumChildren; }
351  size_t& MinNumChildren() { return minNumChildren; }
352 
354  RectangleTree* Parent() const { return parent; }
356  RectangleTree*& Parent() { return parent; }
357 
359  const MatType& Dataset() const { return *dataset; }
361  MatType& Dataset() { return const_cast<MatType&>(*dataset); }
362 
364  MetricType Metric() const { return MetricType(); }
365 
367  void Center(arma::vec& center) { bound.Center(center); }
368 
370  size_t NumChildren() const { return numChildren; }
372  size_t& NumChildren() { return numChildren; }
373 
378  template<typename VecType>
379  size_t GetNearestChild(
380  const VecType& point,
382 
387  template<typename VecType>
388  size_t GetFurthestChild(
389  const VecType& point,
391 
396  size_t GetNearestChild(const RectangleTree& queryNode);
397 
402  size_t GetFurthestChild(const RectangleTree& queryNode);
403 
408  ElemType FurthestPointDistance() const;
409 
417  ElemType FurthestDescendantDistance() const;
418 
422  ElemType MinimumBoundDistance() const { return bound.MinWidth() / 2.0; }
423 
426  ElemType ParentDistance() const { return parentDistance; }
429  ElemType& ParentDistance() { return parentDistance; }
430 
436  inline RectangleTree& Child(const size_t child) const
437  {
438  return *children[child];
439  }
440 
446  inline RectangleTree& Child(const size_t child)
447  {
448  return *children[child];
449  }
450 
453  size_t NumPoints() const;
454 
460  size_t NumDescendants() const;
461 
469  size_t Descendant(const size_t index) const;
470 
479  size_t Point(const size_t index) const { return points[index]; }
480 
483  size_t& Point(const size_t index) { return points[index]; }
484 
486  ElemType MinDistance(const RectangleTree& other) const
487  {
488  return bound.MinDistance(other.Bound());
489  }
490 
492  ElemType MaxDistance(const RectangleTree& other) const
493  {
494  return bound.MaxDistance(other.Bound());
495  }
496 
499  {
500  return bound.RangeDistance(other.Bound());
501  }
502 
504  template<typename VecType>
505  ElemType MinDistance(const VecType& point,
507  const
508  {
509  return bound.MinDistance(point);
510  }
511 
513  template<typename VecType>
514  ElemType MaxDistance(const VecType& point,
516  const
517  {
518  return bound.MaxDistance(point);
519  }
520 
522  template<typename VecType>
524  const VecType& point,
525  typename std::enable_if_t<IsVector<VecType>::value>* = 0) const
526  {
527  return bound.RangeDistance(point);
528  }
529 
533  size_t TreeSize() const;
534 
539  size_t TreeDepth() const;
540 
542  size_t Begin() const { return begin; }
544  size_t& Begin() { return begin; }
545 
547  size_t Count() const { return count; }
549  size_t& Count() { return count; }
550 
551  private:
557  void SplitNode(std::vector<bool>& relevels);
558 
564  void BuildStatistics(RectangleTree* node);
565 
566  protected:
573  RectangleTree();
574 
576  friend class boost::serialization::access;
577 
579  friend DescentType;
580 
582  friend SplitType;
583 
586 
587  public:
599  void CondenseTree(const arma::vec& point,
600  std::vector<bool>& relevels,
601  const bool usePoint);
602 
610  bool ShrinkBoundForPoint(const arma::vec& point);
611 
619  bool ShrinkBoundForBound(const bound::HRectBound<MetricType>& changedBound);
620 
625 
629  template<typename Archive>
630  void serialize(Archive& ar, const unsigned int /* version */);
631 };
632 
633 } // namespace tree
634 } // namespace mlpack
635 
636 // Include implementation.
637 #include "rectangle_tree_impl.hpp"
638 
639 #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:58
ElemType & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
strip_type.hpp
Definition: add_to_po.hpp:21
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:102
const bound::HRectBound< MetricType > & Bound() const
Return the bound object for this node.
MetricType Metric() const
Get the metric which the tree uses.
void serialize(Archive &ar, const unsigned int)
Serialize the tree.
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.
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.
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.