mlpack  2.2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 = NoAuxiliaryInformation>
54 {
55  // The metric *must* be the euclidean distance.
56  static_assert(boost::is_same<MetricType, metric::EuclideanDistance>::value,
57  "RectangleTree: MetricType must be metric::EuclideanDistance.");
58 
59  public:
61  typedef MatType Mat;
63  typedef typename MatType::elem_type ElemType;
65  typedef AuxiliaryInformationType<RectangleTree> AuxiliaryInformation;
66  private:
68  size_t maxNumChildren;
70  size_t minNumChildren;
72  size_t numChildren;
74  std::vector<RectangleTree*> children;
76  RectangleTree* parent;
81  size_t begin;
84  size_t count;
86  size_t numDescendants;
88  size_t maxLeafSize;
90  size_t minLeafSize;
94  StatisticType stat;
96  ElemType parentDistance;
98  const MatType* dataset;
101  bool ownsDataset;
103  std::vector<size_t> points;
105  AuxiliaryInformationType<RectangleTree> auxiliaryInfo;
106 
107  public:
110  template<typename RuleType>
113  template<typename RuleType>
114  class DualTreeTraverser;
115 
130  RectangleTree(const MatType& data,
131  const size_t maxLeafSize = 20,
132  const size_t minLeafSize = 8,
133  const size_t maxNumChildren = 5,
134  const size_t minNumChildren = 2,
135  const size_t firstDataIndex = 0);
136 
151  RectangleTree(MatType&& data,
152  const size_t maxLeafSize = 20,
153  const size_t minLeafSize = 8,
154  const size_t maxNumChildren = 5,
155  const size_t minNumChildren = 2,
156  const size_t firstDataIndex = 0);
157 
166  explicit RectangleTree(RectangleTree* parentNode,
167  const size_t numMaxChildren = 0);
168 
176  RectangleTree(const RectangleTree& other,
177  const bool deepCopy = true,
178  RectangleTree* newParent = NULL);
179 
185  RectangleTree(RectangleTree&& other);
186 
190  template<typename Archive>
192  Archive& ar,
193  const typename boost::enable_if<typename Archive::is_loading>::type* = 0);
194 
200  ~RectangleTree();
201 
207  void SoftDelete();
208 
213  void NullifyData();
214 
220  void InsertPoint(const size_t point);
221 
230  void InsertPoint(const size_t point, std::vector<bool>& relevels);
231 
243  void InsertNode(RectangleTree* node,
244  const size_t level,
245  std::vector<bool>& relevels);
246 
254  bool DeletePoint(const size_t point);
255 
264  bool DeletePoint(const size_t point, std::vector<bool>& relevels);
265 
270  bool RemoveNode(const RectangleTree* node, std::vector<bool>& relevels);
271 
283  const RectangleTree* FindByBeginCount(size_t begin, size_t count) const;
284 
296  RectangleTree* FindByBeginCount(size_t begin, size_t count);
297 
299  const bound::HRectBound<MetricType>& Bound() const { return bound; }
302 
304  const StatisticType& Stat() const { return stat; }
306  StatisticType& Stat() { return stat; }
307 
309  const AuxiliaryInformationType<RectangleTree> &AuxiliaryInfo() const
310  { return auxiliaryInfo; }
312  AuxiliaryInformationType<RectangleTree>& AuxiliaryInfo()
313  { return auxiliaryInfo; }
314 
316  bool IsLeaf() const;
317 
319  size_t MaxLeafSize() const { return maxLeafSize; }
321  size_t& MaxLeafSize() { return maxLeafSize; }
322 
324  size_t MinLeafSize() const { return minLeafSize; }
326  size_t& MinLeafSize() { return minLeafSize; }
327 
329  size_t MaxNumChildren() const { return maxNumChildren; }
331  size_t& MaxNumChildren() { return maxNumChildren; }
332 
334  size_t MinNumChildren() const { return minNumChildren; }
336  size_t& MinNumChildren() { return minNumChildren; }
337 
339  RectangleTree* Parent() const { return parent; }
341  RectangleTree*& Parent() { return parent; }
342 
344  const MatType& Dataset() const { return *dataset; }
346  MatType& Dataset() { return const_cast<MatType&>(*dataset); }
347 
349  MetricType Metric() const { return MetricType(); }
350 
352  void Center(arma::vec& center) { bound.Center(center); }
353 
355  size_t NumChildren() const { return numChildren; }
357  size_t& NumChildren() { return numChildren; }
358 
363  template<typename VecType>
364  size_t GetNearestChild(
365  const VecType& point,
366  typename boost::enable_if<IsVector<VecType> >::type* = 0);
367 
372  template<typename VecType>
373  size_t GetFurthestChild(
374  const VecType& point,
375  typename boost::enable_if<IsVector<VecType> >::type* = 0);
376 
381  size_t GetNearestChild(const RectangleTree& queryNode);
382 
387  size_t GetFurthestChild(const RectangleTree& queryNode);
388 
394 
403 
407  ElemType MinimumBoundDistance() const { return bound.MinWidth() / 2.0; }
408 
411  ElemType ParentDistance() const { return parentDistance; }
414  ElemType& ParentDistance() { return parentDistance; }
415 
421  inline RectangleTree& Child(const size_t child) const
422  {
423  return *children[child];
424  }
425 
431  inline RectangleTree& Child(const size_t child)
432  {
433  return *children[child];
434  }
435 
438  size_t NumPoints() const;
439 
445  size_t NumDescendants() const;
446 
454  size_t Descendant(const size_t index) const;
455 
464  size_t Point(const size_t index) const { return points[index]; }
465 
468  size_t& Point(const size_t index) { return points[index]; }
469 
471  ElemType MinDistance(const RectangleTree& other) const
472  {
473  return bound.MinDistance(other.Bound());
474  }
475 
477  ElemType MaxDistance(const RectangleTree& other) const
478  {
479  return bound.MaxDistance(other.Bound());
480  }
481 
484  {
485  return bound.RangeDistance(other.Bound());
486  }
487 
489  template<typename VecType>
490  ElemType MinDistance(const VecType& point,
491  typename boost::enable_if<IsVector<VecType> >::type* = 0)
492  const
493  {
494  return bound.MinDistance(point);
495  }
496 
498  template<typename VecType>
499  ElemType MaxDistance(const VecType& point,
500  typename boost::enable_if<IsVector<VecType> >::type* = 0)
501  const
502  {
503  return bound.MaxDistance(point);
504  }
505 
507  template<typename VecType>
509  const VecType& point,
510  typename boost::enable_if<IsVector<VecType> >::type* = 0) const
511  {
512  return bound.RangeDistance(point);
513  }
514 
518  size_t TreeSize() const;
519 
524  size_t TreeDepth() const;
525 
527  size_t Begin() const { return begin; }
529  size_t& Begin() { return begin; }
530 
532  size_t Count() const { return count; }
534  size_t& Count() { return count; }
535 
536  private:
542  void SplitNode(std::vector<bool>& relevels);
543 
544  protected:
551  RectangleTree();
552 
554  friend class boost::serialization::access;
555 
557  friend DescentType;
558 
560  friend SplitType;
561 
564 
565  public:
577  void CondenseTree(const arma::vec& point,
578  std::vector<bool>& relevels,
579  const bool usePoint);
580 
588  bool ShrinkBoundForPoint(const arma::vec& point);
589 
597  bool ShrinkBoundForBound(const bound::HRectBound<MetricType>& changedBound);
598 
603 
607  template<typename Archive>
608  void Serialize(Archive& ar, const unsigned int /* version */);
609 };
610 
611 } // namespace tree
612 } // namespace mlpack
613 
614 // Include implementation.
615 #include "rectangle_tree_impl.hpp"
616 
617 #endif
size_t Begin() const
Return the index of the beginning point of this subset.
MatType Mat
So other classes can use TreeType::Mat.
size_t & Count()
Modify the number of points in this subset.
size_t NumChildren() const
Return the number of child nodes. (One level beneath this one only.)
math::RangeType< ElemType > RangeDistance(const RectangleTree &other) const
Return the minimum and maximum distance to another node.
ElemType FurthestDescendantDistance() const
Return the furthest possible descendant distance.
RectangleTree *& Parent()
Modify the parent of this node.
bool ShrinkBoundForPoint(const arma::vec &point)
Shrink the bound object of this node for the removal of a point.
ElemType MinimumBoundDistance() const
Return the minimum distance from the center to any edge of the bound.
ElemType & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
ElemType MinWidth() const
Get the minimum width of the bound.
Definition: hrectbound.hpp:100
size_t MinNumChildren() const
Return the minimum number of children (in a non-leaf node).
The core includes that mlpack expects; standard C++ includes and Armadillo.
const AuxiliaryInformationType< RectangleTree > & AuxiliaryInfo() const
Return the auxiliary information object of this node.
const bound::HRectBound< MetricType > & Bound() const
Return the bound object for this node.
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).
size_t MaxLeafSize() const
Return the maximum leaf size.
friend DescentType
Give friend access for DescentType.
size_t & Begin()
Modify the index of the beginning point of this subset.
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant of this node...
size_t MaxNumChildren() const
Return the maximum number of children (in a non-leaf node).
size_t GetNearestChild(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0)
Return the index of the nearest child node to the given query point.
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 Center(arma::Col< ElemType > &center) const
Calculates the center of the range, placing it into the given vector.
void SoftDelete()
Delete this node of the tree, but leave the stuff contained in it intact.
MetricType Metric() const
Get the metric which the tree uses.
size_t & MinLeafSize()
Modify the minimum leaf size.
size_t TreeDepth() const
Obtains the number of levels below this node in the tree, starting with this.
A rectangle type tree tree, such as an R-tree or X-tree.
size_t NumPoints() const
Return the number of points in this node (returns 0 if this node is not a leaf).
void Serialize(Archive &ar, const unsigned int)
Serialize the tree.
ElemType MinDistance(const RectangleTree &other) const
Return the minimum distance to another node.
size_t GetFurthestChild(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0)
Return the index of the furthest child node to the given query point.
StatisticType & Stat()
Modify the statistic object for this node.
void InsertPoint(const size_t point)
Inserts a point into the tree.
size_t NumDescendants() const
Return the number of descendants of this node.
A dual tree traverser for rectangle type trees.
ElemType MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType >> *=0) const
Calculates maximum bound-to-point squared distance.
size_t Count() const
Return the number of points in this subset.
const StatisticType & Stat() const
Return the statistic object for this node.
~RectangleTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn...
size_t TreeSize() const
Obtains the number of nodes in the tree, starting with this.
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.
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.
math::RangeType< ElemType > RangeDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum and maximum distance to another point.
ElemType MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the maximum distance to another point.
MatType::elem_type ElemType
The element type held by the matrix type.
size_t & NumChildren()
Modify the number of child nodes. Be careful.
A single traverser for rectangle type trees.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
const RectangleTree * FindByBeginCount(size_t begin, size_t count) const
Find a node in this tree by its begin and count (const).
AuxiliaryInformationType< RectangleTree > & AuxiliaryInfo()
Modify the split object of this node.
ElemType ParentDistance() const
Return the distance from the center of this node to the center of the parent 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.
RectangleTree * Parent() const
Gets the parent of this node.
ElemType MinDistance(const VecType &point, typename boost::enable_if< IsVector< VecType >> *=0) const
Calculates minimum bound-to-point distance.
RectangleTree & Child(const size_t child)
Modify the specified child.
const MatType & Dataset() const
Get the dataset which the tree is built on.
ElemType MaxDistance(const RectangleTree &other) const
Return the maximum distance to another node.
LMetric< 2, true > EuclideanDistance
The Euclidean (L2) distance.
Definition: lmetric.hpp:112
size_t & MinNumChildren()
Modify the minimum number of children (in a non-leaf node).
math::RangeType< ElemType > RangeDistance(const HRectBound &other) const
Calculates minimum and maximum bound-to-bound distance.
bound::HRectBound< MetricType > & Bound()
Modify the bound object for this node.
If value == true, then VecType is some sort of Armadillo vector or subview.
Definition: arma_traits.hpp:35
RectangleTree & Child(const size_t child) const
Get the specified child.
size_t MinLeafSize() const
Return the minimum leaf size.
ElemType MinDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum distance to another point.
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.