MLPACK  1.0.11
cover_tree.hpp
Go to the documentation of this file.
1 
22 #ifndef __MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
23 #define __MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
24 
25 #include <mlpack/core.hpp>
27 #include "first_point_is_root.hpp"
28 #include "../statistic.hpp"
29 
30 namespace mlpack {
31 namespace tree {
32 
100 template<typename MetricType = metric::LMetric<2, true>,
101  typename RootPointPolicy = FirstPointIsRoot,
102  typename StatisticType = EmptyStatistic>
104 {
105  public:
106  typedef arma::mat Mat;
107 
118  CoverTree(const arma::mat& dataset,
119  const double base = 2.0,
120  MetricType* metric = NULL);
121 
131  CoverTree(const arma::mat& dataset,
132  MetricType& metric,
133  const double base = 2.0);
134 
166  CoverTree(const arma::mat& dataset,
167  const double base,
168  const size_t pointIndex,
169  const int scale,
170  CoverTree* parent,
171  const double parentDistance,
172  arma::Col<size_t>& indices,
173  arma::vec& distances,
174  size_t nearSetSize,
175  size_t& farSetSize,
176  size_t& usedSetSize,
177  MetricType& metric = NULL);
178 
195  CoverTree(const arma::mat& dataset,
196  const double base,
197  const size_t pointIndex,
198  const int scale,
199  CoverTree* parent,
200  const double parentDistance,
201  const double furthestDescendantDistance,
202  MetricType* metric = NULL);
203 
210  CoverTree(const CoverTree& other);
211 
215  ~CoverTree();
216 
219  template<typename RuleType>
221 
223  template<typename RuleType>
225 
227  const arma::mat& Dataset() const { return dataset; }
228 
230  size_t Point() const { return point; }
232  size_t Point(const size_t) const { return point; }
233 
234  bool IsLeaf() const { return (children.size() == 0); }
235  size_t NumPoints() const { return 1; }
236 
238  const CoverTree& Child(const size_t index) const { return *children[index]; }
240  CoverTree& Child(const size_t index) { return *children[index]; }
241 
243  size_t NumChildren() const { return children.size(); }
244 
246  const std::vector<CoverTree*>& Children() const { return children; }
248  std::vector<CoverTree*>& Children() { return children; }
249 
251  size_t NumDescendants() const;
252 
254  size_t Descendant(const size_t index) const;
255 
257  int Scale() const { return scale; }
259  int& Scale() { return scale; }
260 
262  double Base() const { return base; }
264  double& Base() { return base; }
265 
267  const StatisticType& Stat() const { return stat; }
269  StatisticType& Stat() { return stat; }
270 
272  double MinDistance(const CoverTree* other) const;
273 
276  double MinDistance(const CoverTree* other, const double distance) const;
277 
279  double MinDistance(const arma::vec& other) const;
280 
283  double MinDistance(const arma::vec& other, const double distance) const;
284 
286  double MaxDistance(const CoverTree* other) const;
287 
290  double MaxDistance(const CoverTree* other, const double distance) const;
291 
293  double MaxDistance(const arma::vec& other) const;
294 
297  double MaxDistance(const arma::vec& other, const double distance) const;
298 
300  math::Range RangeDistance(const CoverTree* other) const;
301 
304  math::Range RangeDistance(const CoverTree* other, const double distance)
305  const;
306 
308  math::Range RangeDistance(const arma::vec& other) const;
309 
312  math::Range RangeDistance(const arma::vec& other, const double distance)
313  const;
314 
316  static bool HasSelfChildren() { return true; }
317 
319  CoverTree* Parent() const { return parent; }
321  CoverTree*& Parent() { return parent; }
322 
324  double ParentDistance() const { return parentDistance; }
326  double& ParentDistance() { return parentDistance; }
327 
329  double FurthestPointDistance() const { return 0.0; }
330 
333  { return furthestDescendantDistance; }
337 
341 
343  void Centroid(arma::vec& centroid) const { centroid = dataset.col(point); }
344 
346  MetricType& Metric() const { return *metric; }
347 
348  private:
350  const arma::mat& dataset;
351 
353  size_t point;
354 
356  std::vector<CoverTree*> children;
357 
359  int scale;
360 
362  double base;
363 
365  StatisticType stat;
366 
369 
372 
375 
378 
381 
383  MetricType* metric;
384 
388  void CreateChildren(arma::Col<size_t>& indices,
389  arma::vec& distances,
390  size_t nearSetSize,
391  size_t& farSetSize,
392  size_t& usedSetSize);
393 
405  void ComputeDistances(const size_t pointIndex,
406  const arma::Col<size_t>& indices,
407  arma::vec& distances,
408  const size_t pointSetSize);
423  size_t SplitNearFar(arma::Col<size_t>& indices,
424  arma::vec& distances,
425  const double bound,
426  const size_t pointSetSize);
427 
447  size_t SortPointSet(arma::Col<size_t>& indices,
448  arma::vec& distances,
449  const size_t childFarSetSize,
450  const size_t childUsedSetSize,
451  const size_t farSetSize);
452 
453  void MoveToUsedSet(arma::Col<size_t>& indices,
454  arma::vec& distances,
455  size_t& nearSetSize,
456  size_t& farSetSize,
457  size_t& usedSetSize,
458  arma::Col<size_t>& childIndices,
459  const size_t childFarSetSize,
460  const size_t childUsedSetSize);
461  size_t PruneFarSet(arma::Col<size_t>& indices,
462  arma::vec& distances,
463  const double bound,
464  const size_t nearSetSize,
465  const size_t pointSetSize);
466 
471  void RemoveNewImplicitNodes();
472 
473  public:
477  std::string ToString() const;
478 
479  size_t DistanceComps() const { return distanceComps; }
480  size_t& DistanceComps() { return distanceComps; }
481 
482  private:
484 };
485 
486 }; // namespace tree
487 }; // namespace mlpack
488 
489 // Include implementation.
490 #include "cover_tree_impl.hpp"
491 
492 #endif
math::Range RangeDistance(const CoverTree *other) const
Return the minimum and maximum distance to another node.
std::vector< CoverTree * > children
The list of children; the first is the self-child.
Definition: cover_tree.hpp:356
const arma::mat & dataset
Reference to the matrix which this tree is built on.
Definition: cover_tree.hpp:350
const arma::mat & Dataset() const
Get a reference to the dataset.
Definition: cover_tree.hpp:227
bool localMetric
Whether or not we need to destroy the metric in the destructor.
Definition: cover_tree.hpp:380
StatisticType stat
The instantiated statistic.
Definition: cover_tree.hpp:365
size_t Point() const
Get the index of the point which this node represents.
Definition: cover_tree.hpp:230
int scale
Scale level of the node.
Definition: cover_tree.hpp:359
A dual-tree cover tree traverser; see dual_tree_traverser.hpp.
Definition: cover_tree.hpp:224
CoverTree * parent
The parent node (NULL if this is the root of the tree).
Definition: cover_tree.hpp:371
double MinDistance(const CoverTree *other) const
Return the minimum distance to another node.
static bool HasSelfChildren()
Returns true: this tree does have self-children.
Definition: cover_tree.hpp:316
double MaxDistance(const CoverTree *other) const
Return the maximum distance to another node.
void Centroid(arma::vec &centroid) const
Get the centroid of the node and store it in the given vector.
Definition: cover_tree.hpp:343
size_t numDescendants
The number of descendant points.
Definition: cover_tree.hpp:368
double base
The base used to construct the tree.
Definition: cover_tree.hpp:362
StatisticType & Stat()
Modify the statistic for this node.
Definition: cover_tree.hpp:269
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...
int & Scale()
Modify the scale of this node. Be careful...
Definition: cover_tree.hpp:259
CoverTree(const arma::mat &dataset, const double base=2.0, MetricType *metric=NULL)
Create the cover tree with the given dataset and given base.
const StatisticType & Stat() const
Get the statistic for this node.
Definition: cover_tree.hpp:267
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...
double ParentDistance() const
Get the distance to the parent.
Definition: cover_tree.hpp:324
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 | ...
CoverTree *& Parent()
Modify the parent node.
Definition: cover_tree.hpp:321
double & Base()
Modify the base; don't do this, you'll break everything.
Definition: cover_tree.hpp:264
~CoverTree()
Delete this cover tree node and its children.
int Scale() const
Get the scale of this node.
Definition: cover_tree.hpp:257
size_t DistanceComps() const
Definition: cover_tree.hpp:479
const CoverTree & Child(const size_t index) const
Get a particular child node.
Definition: cover_tree.hpp:238
double & ParentDistance()
Modify the distance to the parent.
Definition: cover_tree.hpp:326
double FurthestDescendantDistance() const
Get the distance from the center of the node to the furthest descendant.
Definition: cover_tree.hpp:332
size_t NumDescendants() const
Get the number of descendant points.
double Base() const
Get the base.
Definition: cover_tree.hpp:262
void RemoveNewImplicitNodes()
Take a look at the last child (the most recently created one) and remove any implicit nodes that have...
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.
A single-tree cover tree traverser; see single_tree_traverser.hpp for implementation.
Definition: cover_tree.hpp:220
double FurthestPointDistance() const
Get the distance to the furthest point. This is always 0 for cover trees.
Definition: cover_tree.hpp:329
std::string ToString() const
Returns a string representation of this object.
double & FurthestDescendantDistance()
Modify the distance from the center of the node to the furthest descendant.
Definition: cover_tree.hpp:336
double parentDistance
Distance to the parent.
Definition: cover_tree.hpp:374
CoverTree & Child(const size_t index)
Modify a particular child node.
Definition: cover_tree.hpp:240
double furthestDescendantDistance
Distance to the furthest descendant.
Definition: cover_tree.hpp:377
CoverTree * Parent() const
Get the parent node.
Definition: cover_tree.hpp:319
double MinimumBoundDistance() const
Get the minimum distance from the center to any bound edge (this is the same as furthestDescendantDis...
Definition: cover_tree.hpp:340
size_t Point(const size_t) const
For compatibility with other trees; the argument is ignored.
Definition: cover_tree.hpp:232
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)
size_t point
Index of the point in the matrix which this node represents.
Definition: cover_tree.hpp:353
size_t NumChildren() const
Get the number of children.
Definition: cover_tree.hpp:243
size_t Descendant(const size_t index) const
Get the index of a particular descendant point.
size_t PruneFarSet(arma::Col< size_t > &indices, arma::vec &distances, const double bound, const size_t nearSetSize, const size_t pointSetSize)
const std::vector< CoverTree * > & Children() const
Get the children.
Definition: cover_tree.hpp:246
A cover tree is a tree specifically designed to speed up nearest-neighbor computation in high-dimensi...
Definition: cover_tree.hpp:103
MetricType & Metric() const
Get the instantiated metric.
Definition: cover_tree.hpp:346
std::vector< CoverTree * > & Children()
Modify the children manually (maybe not a great idea).
Definition: cover_tree.hpp:248
MetricType * metric
The metric used for this tree.
Definition: cover_tree.hpp:383
Simple real-valued range.
Definition: range.hpp:31
size_t NumPoints() const
Definition: cover_tree.hpp:235