22 #ifndef __MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
23 #define __MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
28 #include "../statistic.hpp"
100 template<
typename MetricType = metric::LMetric<2, true>,
101 typename RootPo
intPolicy = FirstPo
intIsRoot,
102 typename StatisticType = EmptyStatistic>
119 const double base = 2.0,
120 MetricType*
metric = NULL);
133 const double base = 2.0);
168 const size_t pointIndex,
172 arma::Col<size_t>& indices,
173 arma::vec& distances,
177 MetricType&
metric = NULL);
197 const size_t pointIndex,
202 MetricType*
metric = NULL);
219 template<
typename RuleType>
223 template<
typename RuleType>
283 double MinDistance(
const arma::vec& other,
const double distance)
const;
297 double MaxDistance(
const arma::vec& other,
const double distance)
const;
385 arma::vec& distances,
388 size_t& usedSetSize);
402 const arma::Col<size_t>& indices,
403 arma::vec& distances,
404 const size_t pointSetSize);
420 arma::vec& distances,
422 const size_t pointSetSize);
444 arma::vec& distances,
445 const size_t childFarSetSize,
446 const size_t childUsedSetSize,
447 const size_t farSetSize);
450 arma::vec& distances,
454 arma::Col<size_t>& childIndices,
455 const size_t childFarSetSize,
456 const size_t childUsedSetSize);
458 arma::vec& distances,
460 const size_t nearSetSize,
461 const size_t pointSetSize);
486 #include "cover_tree_impl.hpp"
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.
const arma::mat & dataset
Reference to the matrix which this tree is built on.
const arma::mat & Dataset() const
Get a reference to the dataset.
bool localMetric
Whether or not we need to destroy the metric in the destructor.
StatisticType stat
The instantiated statistic.
size_t Point() const
Get the index of the point which this node represents.
int scale
Scale level of the node.
A dual-tree cover tree traverser; see dual_tree_traverser.hpp.
CoverTree * parent
The parent node (NULL if this is the root of the tree).
double MinDistance(const CoverTree *other) const
Return the minimum distance to another node.
static bool HasSelfChildren()
Returns true: this tree does have self-children.
double MaxDistance(const CoverTree *other) const
Return the maximum distance to another node.
void Centroid(arma::vec ¢roid) const
Get the centroid of the node and store it in the given vector.
size_t numDescendants
The number of descendant points.
double base
The base used to construct the tree.
StatisticType & Stat()
Modify the statistic for this node.
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...
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.
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.
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.
double & Base()
Modify the base; don't do this, you'll break everything.
~CoverTree()
Delete this cover tree node and its children.
int Scale() const
Get the scale of this node.
size_t DistanceComps() const
const CoverTree & Child(const size_t index) const
Get a particular child node.
double & ParentDistance()
Modify the distance to the parent.
double FurthestDescendantDistance() const
Get the distance from the center of the node to the furthest descendant.
size_t NumDescendants() const
Get the number of descendant points.
double Base() const
Get the base.
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.
double FurthestPointDistance() const
Get the distance to the furthest point. This is always 0 for cover trees.
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.
double parentDistance
Distance to the parent.
CoverTree & Child(const size_t index)
Modify a particular child node.
double furthestDescendantDistance
Distance to the furthest descendant.
CoverTree * Parent() const
Get the parent node.
size_t Point(const size_t) const
For compatibility with other trees; the argument is ignored.
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.
size_t NumChildren() const
Get the number of children.
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.
A cover tree is a tree specifically designed to speed up nearest-neighbor computation in high-dimensi...
MetricType & Metric() const
Get the instantiated metric.
std::vector< CoverTree * > & Children()
Modify the children manually (maybe not a great idea).
MetricType * metric
The metric used for this tree.
Simple real-valued range.