mlpack  2.0.1
cover_tree.hpp
Go to the documentation of this file.
1 
14 #ifndef __MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
15 #define __MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
16 
17 #include <mlpack/core.hpp>
18 
19 #include "../statistic.hpp"
20 #include "first_point_is_root.hpp"
21 
22 namespace mlpack {
23 namespace tree {
24 
94 template<typename MetricType = metric::LMetric<2, true>,
95  typename StatisticType = EmptyStatistic,
96  typename MatType = arma::mat,
97  typename RootPointPolicy = FirstPointIsRoot>
98 class CoverTree
99 {
100  public:
101  typedef MatType Mat;
102 
113  CoverTree(const MatType& dataset,
114  const double base = 2.0,
115  MetricType* metric = NULL);
116 
126  CoverTree(const MatType& dataset,
127  MetricType& metric,
128  const double base = 2.0);
129 
137  CoverTree(MatType&& dataset,
138  const double base = 2.0);
139 
148  CoverTree(MatType&& dataset,
149  MetricType& metric,
150  const double base = 2.0);
151 
183  CoverTree(const MatType& dataset,
184  const double base,
185  const size_t pointIndex,
186  const int scale,
187  CoverTree* parent,
188  const double parentDistance,
189  arma::Col<size_t>& indices,
190  arma::vec& distances,
191  size_t nearSetSize,
192  size_t& farSetSize,
193  size_t& usedSetSize,
194  MetricType& metric = NULL);
195 
212  CoverTree(const MatType& dataset,
213  const double base,
214  const size_t pointIndex,
215  const int scale,
216  CoverTree* parent,
217  const double parentDistance,
218  const double furthestDescendantDistance,
219  MetricType* metric = NULL);
220 
227  CoverTree(const CoverTree& other);
228 
232  template<typename Archive>
233  CoverTree(
234  Archive& ar,
235  const typename boost::enable_if<typename Archive::is_loading>::type* = 0);
236 
240  ~CoverTree();
241 
244  template<typename RuleType>
246 
248  template<typename RuleType>
250 
251  template<typename RuleType>
253 
255  const MatType& Dataset() const { return *dataset; }
256 
258  size_t Point() const { return point; }
260  size_t Point(const size_t) const { return point; }
261 
262  bool IsLeaf() const { return (children.size() == 0); }
263  size_t NumPoints() const { return 1; }
264 
266  const CoverTree& Child(const size_t index) const { return *children[index]; }
268  CoverTree& Child(const size_t index) { return *children[index]; }
269 
270  CoverTree*& ChildPtr(const size_t index) { return children[index]; }
271 
273  size_t NumChildren() const { return children.size(); }
274 
276  const std::vector<CoverTree*>& Children() const { return children; }
278  std::vector<CoverTree*>& Children() { return children; }
279 
281  size_t NumDescendants() const;
282 
284  size_t Descendant(const size_t index) const;
285 
287  int Scale() const { return scale; }
289  int& Scale() { return scale; }
290 
292  double Base() const { return base; }
294  double& Base() { return base; }
295 
297  const StatisticType& Stat() const { return stat; }
299  StatisticType& Stat() { return stat; }
300 
302  double MinDistance(const CoverTree* other) const;
303 
306  double MinDistance(const CoverTree* other, const double distance) const;
307 
309  double MinDistance(const arma::vec& other) const;
310 
313  double MinDistance(const arma::vec& other, const double distance) const;
314 
316  double MaxDistance(const CoverTree* other) const;
317 
320  double MaxDistance(const CoverTree* other, const double distance) const;
321 
323  double MaxDistance(const arma::vec& other) const;
324 
327  double MaxDistance(const arma::vec& other, const double distance) const;
328 
330  math::Range RangeDistance(const CoverTree* other) const;
331 
334  math::Range RangeDistance(const CoverTree* other, const double distance)
335  const;
336 
338  math::Range RangeDistance(const arma::vec& other) const;
339 
342  math::Range RangeDistance(const arma::vec& other, const double distance)
343  const;
344 
346  static bool HasSelfChildren() { return true; }
347 
349  CoverTree* Parent() const { return parent; }
351  CoverTree*& Parent() { return parent; }
352 
354  double ParentDistance() const { return parentDistance; }
356  double& ParentDistance() { return parentDistance; }
357 
359  double FurthestPointDistance() const { return 0.0; }
360 
363  { return furthestDescendantDistance; }
367 
371 
373  void Center(arma::vec& center) const
374  {
375  center = arma::vec(dataset->col(point));
376  }
377 
379  MetricType& Metric() const { return *metric; }
380 
381  private:
383  const MatType* dataset;
385  size_t point;
387  std::vector<CoverTree*> children;
389  int scale;
391  double base;
393  StatisticType stat;
407  MetricType* metric;
408 
412  void CreateChildren(arma::Col<size_t>& indices,
413  arma::vec& distances,
414  size_t nearSetSize,
415  size_t& farSetSize,
416  size_t& usedSetSize);
417 
429  void ComputeDistances(const size_t pointIndex,
430  const arma::Col<size_t>& indices,
431  arma::vec& distances,
432  const size_t pointSetSize);
447  size_t SplitNearFar(arma::Col<size_t>& indices,
448  arma::vec& distances,
449  const double bound,
450  const size_t pointSetSize);
451 
471  size_t SortPointSet(arma::Col<size_t>& indices,
472  arma::vec& distances,
473  const size_t childFarSetSize,
474  const size_t childUsedSetSize,
475  const size_t farSetSize);
476 
477  void MoveToUsedSet(arma::Col<size_t>& indices,
478  arma::vec& distances,
479  size_t& nearSetSize,
480  size_t& farSetSize,
481  size_t& usedSetSize,
482  arma::Col<size_t>& childIndices,
483  const size_t childFarSetSize,
484  const size_t childUsedSetSize);
485  size_t PruneFarSet(arma::Col<size_t>& indices,
486  arma::vec& distances,
487  const double bound,
488  const size_t nearSetSize,
489  const size_t pointSetSize);
490 
495  void RemoveNewImplicitNodes();
496 
497  protected:
504  CoverTree();
505 
507  friend class boost::serialization::access;
508 
509  public:
513  template<typename Archive>
514  void Serialize(Archive& ar, const unsigned int /* version */);
515 
516  size_t DistanceComps() const { return distanceComps; }
517  size_t& DistanceComps() { return distanceComps; }
518 
519  private:
521 };
522 
523 } // namespace tree
524 } // namespace mlpack
525 
526 // Include implementation.
527 #include "cover_tree_impl.hpp"
528 
529 // Include the rest of the pieces, if necessary.
530 #include "../cover_tree.hpp"
531 
532 #endif
double MinimumBoundDistance() const
Get the minimum distance from the center to any bound edge (this is the same as furthestDescendantDis...
Definition: cover_tree.hpp:370
void Center(arma::vec &center) const
Get the center of the node and store it in the given vector.
Definition: cover_tree.hpp:373
size_t point
Index of the point in the matrix which this node represents.
Definition: cover_tree.hpp:385
const MatType * dataset
Reference to the matrix which this tree is built on.
Definition: cover_tree.hpp:383
const std::vector< CoverTree * > & Children() const
Get the children.
Definition: cover_tree.hpp:276
CoverTree()
A default constructor.
StatisticType & Stat()
Modify the statistic for this node.
Definition: cover_tree.hpp:299
std::vector< CoverTree * > & Children()
Modify the children manually (maybe not a great idea).
Definition: cover_tree.hpp:278
size_t SortPointSet(arma::Col< size_t > &indices, arma::vec &distances, const size_t childFarSetSize, const size_t childUsedSetSize, const size_t farSetSize)
Assuming that the list of indices and distances is sorted as [ childFarSet | childUsedSet | farSet | ...
double Base() const
Get the base.
Definition: cover_tree.hpp:292
size_t Point(const size_t) const
For compatibility with other trees; the argument is ignored.
Definition: cover_tree.hpp:260
MetricType * metric
The metric used for this tree.
Definition: cover_tree.hpp:407
size_t Descendant(const size_t index) const
Get the index of a particular descendant point.
A dual-tree cover tree traverser; see dual_tree_traverser.hpp.
Definition: cover_tree.hpp:249
StatisticType stat
The instantiated statistic.
Definition: cover_tree.hpp:393
const MatType & Dataset() const
Get a reference to the dataset.
Definition: cover_tree.hpp:255
void RemoveNewImplicitNodes()
Take a look at the last child (the most recently created one) and remove any implicit nodes that have...
double base
The base used to construct the tree.
Definition: cover_tree.hpp:391
double MaxDistance(const CoverTree *other) const
Return the maximum distance to another node.
Linear algebra utility functions, generally performed on matrices or vectors.
size_t NumPoints() const
Definition: cover_tree.hpp:263
size_t NumDescendants() const
Get the number of descendant points.
double parentDistance
Distance to the parent.
Definition: cover_tree.hpp:399
double furthestDescendantDistance
Distance to the furthest descendant.
Definition: cover_tree.hpp:401
void ComputeDistances(const size_t pointIndex, const arma::Col< size_t > &indices, arma::vec &distances, const size_t pointSetSize)
Fill the vector of distances with the distances between the point specified by pointIndex and each po...
MetricType & Metric() const
Get the instantiated metric.
Definition: cover_tree.hpp:379
double FurthestPointDistance() const
Get the distance to the furthest point. This is always 0 for cover trees.
Definition: cover_tree.hpp:359
double ParentDistance() const
Get the distance to the parent.
Definition: cover_tree.hpp:354
void Serialize(Archive &ar, const unsigned int)
Serialize the tree.
double & ParentDistance()
Modify the distance to the parent.
Definition: cover_tree.hpp:356
CoverTree *& Parent()
Modify the parent node.
Definition: cover_tree.hpp:351
size_t NumChildren() const
Get the number of children.
Definition: cover_tree.hpp:273
Simple real-valued range.
Definition: range.hpp:21
int & Scale()
Modify the scale of this node. Be careful...
Definition: cover_tree.hpp:289
const StatisticType & Stat() const
Get the statistic for this node.
Definition: cover_tree.hpp:297
size_t PruneFarSet(arma::Col< size_t > &indices, arma::vec &distances, const double bound, const size_t nearSetSize, const size_t pointSetSize)
CoverTree * parent
The parent node (NULL if this is the root of the tree).
Definition: cover_tree.hpp:397
math::Range RangeDistance(const CoverTree *other) const
Return the minimum and maximum distance to another node.
Include all of the base components required to write MLPACK methods, and the main MLPACK Doxygen docu...
A single-tree cover tree traverser; see single_tree_traverser.hpp for implementation.
Definition: cover_tree.hpp:245
int scale
Scale level of the node.
Definition: cover_tree.hpp:389
std::vector< CoverTree * > children
The list of children; the first is the self-child.
Definition: cover_tree.hpp:387
double & Base()
Modify the base; don't do this, you'll break everything.
Definition: cover_tree.hpp:294
static bool HasSelfChildren()
Returns true: this tree does have self-children.
Definition: cover_tree.hpp:346
double & FurthestDescendantDistance()
Modify the distance from the center of the node to the furthest descendant.
Definition: cover_tree.hpp:366
double MinDistance(const CoverTree *other) const
Return the minimum distance to another node.
const CoverTree & Child(const size_t index) const
Get a particular child node.
Definition: cover_tree.hpp:266
size_t Point() const
Get the index of the point which this node represents.
Definition: cover_tree.hpp:258
size_t SplitNearFar(arma::Col< size_t > &indices, arma::vec &distances, const double bound, const size_t pointSetSize)
Split the given indices and distances into a near and a far set, returning the number of points in th...
size_t numDescendants
The number of descendant points.
Definition: cover_tree.hpp:395
bool localDataset
If true, we own the dataset and need to destroy it in the destructor.
Definition: cover_tree.hpp:405
size_t DistanceComps() const
Definition: cover_tree.hpp:516
A cover tree is a tree specifically designed to speed up nearest-neighbor computation in high-dimensi...
Definition: cover_tree.hpp:98
void CreateChildren(arma::Col< size_t > &indices, arma::vec &distances, size_t nearSetSize, size_t &farSetSize, size_t &usedSetSize)
Create the children for this node.
CoverTree & Child(const size_t index)
Modify a particular child node.
Definition: cover_tree.hpp:268
double FurthestDescendantDistance() const
Get the distance from the center of the node to the furthest descendant.
Definition: cover_tree.hpp:362
CoverTree *& ChildPtr(const size_t index)
Definition: cover_tree.hpp:270
CoverTree * Parent() const
Get the parent node.
Definition: cover_tree.hpp:349
~CoverTree()
Delete this cover tree node and its children.
bool localMetric
Whether or not we need to destroy the metric in the destructor.
Definition: cover_tree.hpp:403
int Scale() const
Get the scale of this node.
Definition: cover_tree.hpp:287
void MoveToUsedSet(arma::Col< size_t > &indices, arma::vec &distances, size_t &nearSetSize, size_t &farSetSize, size_t &usedSetSize, arma::Col< size_t > &childIndices, const size_t childFarSetSize, const size_t childUsedSetSize)