mlpack  1.0.12
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>
19 #include "first_point_is_root.hpp"
20 #include "../statistic.hpp"
21 
22 namespace mlpack {
23 namespace tree {
24 
92 template<typename MetricType = metric::LMetric<2, true>,
93  typename RootPointPolicy = FirstPointIsRoot,
94  typename StatisticType = EmptyStatistic>
95 class CoverTree
96 {
97  public:
98  typedef arma::mat Mat;
99 
110  CoverTree(const arma::mat& dataset,
111  const double base = 2.0,
112  MetricType* metric = NULL);
113 
123  CoverTree(const arma::mat& dataset,
124  MetricType& metric,
125  const double base = 2.0);
126 
158  CoverTree(const arma::mat& dataset,
159  const double base,
160  const size_t pointIndex,
161  const int scale,
162  CoverTree* parent,
163  const double parentDistance,
164  arma::Col<size_t>& indices,
165  arma::vec& distances,
166  size_t nearSetSize,
167  size_t& farSetSize,
168  size_t& usedSetSize,
169  MetricType& metric = NULL);
170 
187  CoverTree(const arma::mat& dataset,
188  const double base,
189  const size_t pointIndex,
190  const int scale,
191  CoverTree* parent,
192  const double parentDistance,
193  const double furthestDescendantDistance,
194  MetricType* metric = NULL);
195 
202  CoverTree(const CoverTree& other);
203 
207  ~CoverTree();
208 
211  template<typename RuleType>
213 
215  template<typename RuleType>
217 
219  const arma::mat& Dataset() const { return dataset; }
220 
222  size_t Point() const { return point; }
224  size_t Point(const size_t) const { return point; }
225 
226  bool IsLeaf() const { return (children.size() == 0); }
227  size_t NumPoints() const { return 1; }
228 
230  const CoverTree& Child(const size_t index) const { return *children[index]; }
232  CoverTree& Child(const size_t index) { return *children[index]; }
233 
235  size_t NumChildren() const { return children.size(); }
236 
238  const std::vector<CoverTree*>& Children() const { return children; }
240  std::vector<CoverTree*>& Children() { return children; }
241 
243  size_t NumDescendants() const;
244 
246  size_t Descendant(const size_t index) const;
247 
249  int Scale() const { return scale; }
251  int& Scale() { return scale; }
252 
254  double Base() const { return base; }
256  double& Base() { return base; }
257 
259  const StatisticType& Stat() const { return stat; }
261  StatisticType& Stat() { return stat; }
262 
264  double MinDistance(const CoverTree* other) const;
265 
268  double MinDistance(const CoverTree* other, const double distance) const;
269 
271  double MinDistance(const arma::vec& other) const;
272 
275  double MinDistance(const arma::vec& other, const double distance) const;
276 
278  double MaxDistance(const CoverTree* other) const;
279 
282  double MaxDistance(const CoverTree* other, const double distance) const;
283 
285  double MaxDistance(const arma::vec& other) const;
286 
289  double MaxDistance(const arma::vec& other, const double distance) const;
290 
292  math::Range RangeDistance(const CoverTree* other) const;
293 
296  math::Range RangeDistance(const CoverTree* other, const double distance)
297  const;
298 
300  math::Range RangeDistance(const arma::vec& other) const;
301 
304  math::Range RangeDistance(const arma::vec& other, const double distance)
305  const;
306 
308  static bool HasSelfChildren() { return true; }
309 
311  CoverTree* Parent() const { return parent; }
313  CoverTree*& Parent() { return parent; }
314 
316  double ParentDistance() const { return parentDistance; }
318  double& ParentDistance() { return parentDistance; }
319 
321  double FurthestPointDistance() const { return 0.0; }
322 
325  { return furthestDescendantDistance; }
329 
333 
335  void Centroid(arma::vec& centroid) const { centroid = dataset.col(point); }
336 
338  MetricType& Metric() const { return *metric; }
339 
340  private:
342  const arma::mat& dataset;
343 
345  size_t point;
346 
348  std::vector<CoverTree*> children;
349 
351  int scale;
352 
354  double base;
355 
357  StatisticType stat;
358 
361 
364 
367 
370 
373 
375  MetricType* metric;
376 
380  void CreateChildren(arma::Col<size_t>& indices,
381  arma::vec& distances,
382  size_t nearSetSize,
383  size_t& farSetSize,
384  size_t& usedSetSize);
385 
397  void ComputeDistances(const size_t pointIndex,
398  const arma::Col<size_t>& indices,
399  arma::vec& distances,
400  const size_t pointSetSize);
415  size_t SplitNearFar(arma::Col<size_t>& indices,
416  arma::vec& distances,
417  const double bound,
418  const size_t pointSetSize);
419 
439  size_t SortPointSet(arma::Col<size_t>& indices,
440  arma::vec& distances,
441  const size_t childFarSetSize,
442  const size_t childUsedSetSize,
443  const size_t farSetSize);
444 
445  void MoveToUsedSet(arma::Col<size_t>& indices,
446  arma::vec& distances,
447  size_t& nearSetSize,
448  size_t& farSetSize,
449  size_t& usedSetSize,
450  arma::Col<size_t>& childIndices,
451  const size_t childFarSetSize,
452  const size_t childUsedSetSize);
453  size_t PruneFarSet(arma::Col<size_t>& indices,
454  arma::vec& distances,
455  const double bound,
456  const size_t nearSetSize,
457  const size_t pointSetSize);
458 
463  void RemoveNewImplicitNodes();
464 
465  public:
469  std::string ToString() const;
470 
471  size_t DistanceComps() const { return distanceComps; }
472  size_t& DistanceComps() { return distanceComps; }
473 
474  private:
476 };
477 
478 }; // namespace tree
479 }; // namespace mlpack
480 
481 // Include implementation.
482 #include "cover_tree_impl.hpp"
483 
484 #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:348
const arma::mat & dataset
Reference to the matrix which this tree is built on.
Definition: cover_tree.hpp:342
const arma::mat & Dataset() const
Get a reference to the dataset.
Definition: cover_tree.hpp:219
bool localMetric
Whether or not we need to destroy the metric in the destructor.
Definition: cover_tree.hpp:372
StatisticType stat
The instantiated statistic.
Definition: cover_tree.hpp:357
size_t Point() const
Get the index of the point which this node represents.
Definition: cover_tree.hpp:222
int scale
Scale level of the node.
Definition: cover_tree.hpp:351
A dual-tree cover tree traverser; see dual_tree_traverser.hpp.
Definition: cover_tree.hpp:216
CoverTree * parent
The parent node (NULL if this is the root of the tree).
Definition: cover_tree.hpp:363
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: load.hpp:23
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:308
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:335
size_t numDescendants
The number of descendant points.
Definition: cover_tree.hpp:360
double base
The base used to construct the tree.
Definition: cover_tree.hpp:354
StatisticType & Stat()
Modify the statistic for this node.
Definition: cover_tree.hpp:261
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:251
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:259
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:316
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:313
double & Base()
Modify the base; don't do this, you'll break everything.
Definition: cover_tree.hpp:256
~CoverTree()
Delete this cover tree node and its children.
int Scale() const
Get the scale of this node.
Definition: cover_tree.hpp:249
size_t DistanceComps() const
Definition: cover_tree.hpp:471
const CoverTree & Child(const size_t index) const
Get a particular child node.
Definition: cover_tree.hpp:230
double & ParentDistance()
Modify the distance to the parent.
Definition: cover_tree.hpp:318
double FurthestDescendantDistance() const
Get the distance from the center of the node to the furthest descendant.
Definition: cover_tree.hpp:324
size_t NumDescendants() const
Get the number of descendant points.
double Base() const
Get the base.
Definition: cover_tree.hpp:254
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:212
double FurthestPointDistance() const
Get the distance to the furthest point. This is always 0 for cover trees.
Definition: cover_tree.hpp:321
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:328
double parentDistance
Distance to the parent.
Definition: cover_tree.hpp:366
CoverTree & Child(const size_t index)
Modify a particular child node.
Definition: cover_tree.hpp:232
double furthestDescendantDistance
Distance to the furthest descendant.
Definition: cover_tree.hpp:369
CoverTree * Parent() const
Get the parent node.
Definition: cover_tree.hpp:311
double MinimumBoundDistance() const
Get the minimum distance from the center to any bound edge (this is the same as furthestDescendantDis...
Definition: cover_tree.hpp:332
size_t Point(const size_t) const
For compatibility with other trees; the argument is ignored.
Definition: cover_tree.hpp:224
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:345
size_t NumChildren() const
Get the number of children.
Definition: cover_tree.hpp:235
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:238
A cover tree is a tree specifically designed to speed up nearest-neighbor computation in high-dimensi...
Definition: cover_tree.hpp:95
MetricType & Metric() const
Get the instantiated metric.
Definition: cover_tree.hpp:338
std::vector< CoverTree * > & Children()
Modify the children manually (maybe not a great idea).
Definition: cover_tree.hpp:240
MetricType * metric
The metric used for this tree.
Definition: cover_tree.hpp:375
Simple real-valued range.
Definition: range.hpp:23
size_t NumPoints() const
Definition: cover_tree.hpp:227