MLPACK  1.0.7
Classes | Public Types | Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes | List of all members
mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType > Class Template Reference

A cover tree is a tree specifically designed to speed up nearest-neighbor computation in high-dimensional spaces. More...

Collaboration diagram for mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >:
Collaboration graph
[legend]

Classes

class  DualTreeTraverser
 A dual-tree cover tree traverser; see dual_tree_traverser.hpp. More...
 
class  SingleTreeTraverser
 A single-tree cover tree traverser; see single_tree_traverser.hpp for implementation. More...
 

Public Types

typedef arma::mat Mat
 

Public Member Functions

 CoverTree (const arma::mat &dataset, const double base=2.0, MetricType *metric=NULL)
 Create the cover tree with the given dataset and given base. More...
 
 CoverTree (const arma::mat &dataset, MetricType &metric, const double base=2.0)
 Create the cover tree with the given dataset and the given instantiated metric. More...
 
 CoverTree (const arma::mat &dataset, const double base, const size_t pointIndex, const int scale, CoverTree *parent, const double parentDistance, arma::Col< size_t > &indices, arma::vec &distances, size_t nearSetSize, size_t &farSetSize, size_t &usedSetSize, MetricType &metric=NULL)
 Construct a child cover tree node. More...
 
 CoverTree (const arma::mat &dataset, const double base, const size_t pointIndex, const int scale, CoverTree *parent, const double parentDistance, const double furthestDescendantDistance, MetricType *metric=NULL)
 Manually construct a cover tree node; no tree assembly is done in this constructor, and children must be added manually (use Children()). More...
 
 CoverTree (const CoverTree &other)
 Create a cover tree from another tree. More...
 
 ~CoverTree ()
 Delete this cover tree node and its children. More...
 
double Base () const
 Get the base. More...
 
double & Base ()
 Modify the base; don't do this, you'll break everything. More...
 
void Centroid (arma::vec &centroid) const
 Get the centroid of the node and store it in the given vector. More...
 
const CoverTreeChild (const size_t index) const
 Get a particular child node. More...
 
CoverTreeChild (const size_t index)
 Modify a particular child node. More...
 
const std::vector< CoverTree * > & Children () const
 Get the children. More...
 
std::vector< CoverTree * > & Children ()
 Modify the children manually (maybe not a great idea). More...
 
const arma::mat & Dataset () const
 Get a reference to the dataset. More...
 
size_t Descendant (const size_t index) const
 Get the index of a particular descendant point. More...
 
size_t DistanceComps () const
 
size_t & DistanceComps ()
 
double FurthestDescendantDistance () const
 Get the distance to the furthest descendant. More...
 
double & FurthestDescendantDistance ()
 Modify the distance to the furthest descendant. More...
 
bool IsLeaf () const
 
double MaxDistance (const CoverTree *other) const
 Return the maximum distance to another node. More...
 
double MaxDistance (const CoverTree *other, const double distance) const
 Return the maximum distance to another node given that the point-to-point distance has already been calculated. More...
 
double MaxDistance (const arma::vec &other) const
 Return the maximum distance to another point. More...
 
double MaxDistance (const arma::vec &other, const double distance) const
 Return the maximum distance to another point given that the distance from the center to the point has already been calculated. More...
 
MetricType & Metric () const
 Get the instantiated metric. More...
 
double MinDistance (const CoverTree *other) const
 Return the minimum distance to another node. More...
 
double MinDistance (const CoverTree *other, const double distance) const
 Return the minimum distance to another node given that the point-to-point distance has already been calculated. More...
 
double MinDistance (const arma::vec &other) const
 Return the minimum distance to another point. More...
 
double MinDistance (const arma::vec &other, const double distance) const
 Return the minimum distance to another point given that the distance from the center to the point has already been calculated. More...
 
size_t NumChildren () const
 Get the number of children. More...
 
size_t NumDescendants () const
 Get the number of descendant points. More...
 
size_t NumPoints () const
 
CoverTreeParent () const
 Get the parent node. More...
 
CoverTree *& Parent ()
 Modify the parent node. More...
 
double ParentDistance () const
 Get the distance to the parent. More...
 
double & ParentDistance ()
 Modify the distance to the parent. More...
 
size_t Point () const
 Get the index of the point which this node represents. More...
 
size_t Point (const size_t) const
 For compatibility with other trees; the argument is ignored. More...
 
math::Range RangeDistance (const CoverTree *other) const
 Return the minimum and maximum distance to another node. More...
 
math::Range RangeDistance (const CoverTree *other, const double distance) const
 Return the minimum and maximum distance to another node given that the point-to-point distance has already been calculated. More...
 
math::Range RangeDistance (const arma::vec &other) const
 Return the minimum and maximum distance to another point. More...
 
math::Range RangeDistance (const arma::vec &other, const double distance) const
 Return the minimum and maximum distance to another point given that the point-to-point distance has already been calculated. More...
 
int Scale () const
 Get the scale of this node. More...
 
int & Scale ()
 Modify the scale of this node. Be careful... More...
 
const StatisticType & Stat () const
 Get the statistic for this node. More...
 
StatisticType & Stat ()
 Modify the statistic for this node. More...
 
std::string ToString () const
 Returns a string representation of this object. More...
 

Static Public Member Functions

static bool HasSelfChildren ()
 Returns true: this tree does have self-children. More...
 

Private Member Functions

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 point in the indices array. More...
 
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. More...
 
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 PruneFarSet (arma::Col< size_t > &indices, arma::vec &distances, const double bound, const size_t nearSetSize, const size_t pointSetSize)
 
void RemoveNewImplicitNodes ()
 Take a look at the last child (the most recently created one) and remove any implicit nodes that have been created. More...
 
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 | usedSet ], resort the sets so the organization is [ childFarSet | farSet | childUsedSet | usedSet ]. More...
 
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 the near set. More...
 

Private Attributes

double base
 The base used to construct the tree. More...
 
std::vector< CoverTree * > children
 The list of children; the first is the self-child. More...
 
const arma::mat & dataset
 Reference to the matrix which this tree is built on. More...
 
size_t distanceComps
 
double furthestDescendantDistance
 Distance to the furthest descendant. More...
 
bool localMetric
 Whether or not we need to destroy the metric in the destructor. More...
 
MetricType * metric
 The metric used for this tree. More...
 
size_t numDescendants
 The number of descendant points. More...
 
CoverTreeparent
 The parent node (NULL if this is the root of the tree). More...
 
double parentDistance
 Distance to the parent. More...
 
size_t point
 Index of the point in the matrix which this node represents. More...
 
int scale
 Scale level of the node. More...
 
StatisticType stat
 The instantiated statistic. More...
 

Detailed Description

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
class mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >

A cover tree is a tree specifically designed to speed up nearest-neighbor computation in high-dimensional spaces.

Each non-leaf node references a point and has a nonzero number of children, including a "self-child" which references the same point. A leaf node represents only one point.

The tree can be thought of as a hierarchy with the root node at the top level and the leaf nodes at the bottom level. Each level in the tree has an assigned 'scale' i. The tree follows these three conditions:

The value 'b' refers to the base, which is a parameter of the tree. These three properties make the cover tree very good for fast, high-dimensional nearest-neighbor search.

The theoretical structure of the tree contains many 'implicit' nodes which only have a "self-child" (a child referencing the same point, but at a lower scale level). This practical implementation only constructs explicit nodes – non-leaf nodes with more than one child. A leaf node has no children, and its scale level is INT_MIN.

For more information on cover trees, see

* @inproceedings{
* author = {Beygelzimer, Alina and Kakade, Sham and Langford, John},
* title = {Cover trees for nearest neighbor},
* booktitle = {Proceedings of the 23rd International Conference on Machine
* Learning},
* series = {ICML '06},
* year = {2006},
* pages = {97--104]
* }
*

For information on runtime bounds of the nearest-neighbor computation using cover trees, see the following paper, presented at NIPS 2009:

* @inproceedings{
* author = {Ram, P., and Lee, D., and March, W.B., and Gray, A.G.},
* title = {Linear-time Algorithms for Pairwise Statistical Problems},
* booktitle = {Advances in Neural Information Processing Systems 22},
* editor = {Y. Bengio and D. Schuurmans and J. Lafferty and C.K.I. Williams
* and A. Culotta},
* pages = {1527--1535},
* year = {2009}
* }
*

The CoverTree class offers three template parameters; a custom metric type can be used with MetricType (this class defaults to the L2-squared metric). The root node's point can be chosen with the RootPointPolicy; by default, the FirstPointIsRoot policy is used, meaning the first point in the dataset is used. The StatisticType policy allows you to define statistics which can be gathered during the creation of the tree.

Template Parameters
MetricTypeMetric type to use during tree construction.
RootPointPolicyDetermines which point to use as the root node.
StatisticTypeStatistic to be used during tree creation.

Definition at line 103 of file cover_tree.hpp.

Member Typedef Documentation

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
typedef arma::mat mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Mat

Definition at line 106 of file cover_tree.hpp.

Constructor & Destructor Documentation

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::CoverTree ( const arma::mat &  dataset,
const double  base = 2.0,
MetricType *  metric = NULL 
)

Create the cover tree with the given dataset and given base.

The dataset will not be modified during the building procedure (unlike BinarySpaceTree).

The last argument will be removed in mlpack 1.1.0 (see #274 and #273).

Parameters
datasetReference to the dataset to build a tree on.
baseBase to use during tree building (default 2.0).
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::CoverTree ( const arma::mat &  dataset,
MetricType &  metric,
const double  base = 2.0 
)

Create the cover tree with the given dataset and the given instantiated metric.

Optionally, set the base. The dataset will not be modified during the building procedure (unlike BinarySpaceTree).

Parameters
datasetReference to the dataset to build a tree on.
metricInstantiated metric to use during tree building.
baseBase to use during tree building (default 2.0).
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::CoverTree ( const arma::mat &  dataset,
const double  base,
const size_t  pointIndex,
const int  scale,
CoverTree< MetricType, RootPointPolicy, StatisticType > *  parent,
const double  parentDistance,
arma::Col< size_t > &  indices,
arma::vec &  distances,
size_t  nearSetSize,
size_t &  farSetSize,
size_t &  usedSetSize,
MetricType &  metric = NULL 
)

Construct a child cover tree node.

This constructor is not meant to be used externally, but it could be used to insert another node into a tree. This procedure uses only one vector for the near set, the far set, and the used set (this is to prevent unnecessary memory allocation in recursive calls to this constructor). Therefore, the size of the near set, far set, and used set must be passed in. The near set will be entirely used up, and some of the far set may be used. The value of usedSetSize will be set to the number of points used in the construction of this node, and the value of farSetSize will be modified to reflect the number of points in the far set after the construction of this node.

If you are calling this manually, be careful that the given scale is as small as possible, or you may be creating an implicit node in your tree.

Parameters
datasetReference to the dataset to build a tree on.
baseBase to use during tree building.
pointIndexIndex of the point this node references.
scaleScale of this level in the tree.
parentParent of this node (NULL indicates no parent).
parentDistanceDistance to the parent node.
indicesArray of indices, ordered [ nearSet | farSet | usedSet ]; will be modified to [ farSet | usedSet ].
distancesArray of distances, ordered the same way as the indices. These represent the distances between the point specified by pointIndex and each point in the indices array.
nearSetSizeSize of the near set; if 0, this will be a leaf.
farSetSizeSize of the far set; may be modified (if this node uses any points in the far set).
usedSetSizeThe number of points used will be added to this number.
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::CoverTree ( const arma::mat &  dataset,
const double  base,
const size_t  pointIndex,
const int  scale,
CoverTree< MetricType, RootPointPolicy, StatisticType > *  parent,
const double  parentDistance,
const double  furthestDescendantDistance,
MetricType *  metric = NULL 
)

Manually construct a cover tree node; no tree assembly is done in this constructor, and children must be added manually (use Children()).

This constructor is useful when the tree is being "imported" into the CoverTree class after being created in some other manner.

Parameters
datasetReference to the dataset this node is a part of.
baseBase that was used for tree building.
pointIndexIndex of the point in the dataset which this node refers to.
scaleScale of this node's level in the tree.
parentParent node (NULL indicates no parent).
parentDistanceDistance to parent node point.
furthestDescendantDistanceDistance to furthest descendant point.
metricInstantiated metric (optional).
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::CoverTree ( const CoverTree< MetricType, RootPointPolicy, StatisticType > &  other)

Create a cover tree from another tree.

Be careful! This may use a lot of memory and take a lot of time.

Parameters
otherCover tree to copy from.
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::~CoverTree ( )

Delete this cover tree node and its children.

Member Function Documentation

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Base ( ) const
inline
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Base ( )
inline

Modify the base; don't do this, you'll break everything.

Definition at line 264 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::base.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
void mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Centroid ( arma::vec &  centroid) const
inline
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
const CoverTree& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Child ( const size_t  index) const
inline

Get a particular child node.

Definition at line 238 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::children.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
CoverTree& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Child ( const size_t  index)
inline

Modify a particular child node.

Definition at line 240 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::children.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
const std::vector<CoverTree*>& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Children ( ) const
inline
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
std::vector<CoverTree*>& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Children ( )
inline

Modify the children manually (maybe not a great idea).

Definition at line 248 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::children.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
void mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::ComputeDistances ( const size_t  pointIndex,
const arma::Col< size_t > &  indices,
arma::vec &  distances,
const size_t  pointSetSize 
)
private

Fill the vector of distances with the distances between the point specified by pointIndex and each point in the indices array.

The distances of the first pointSetSize points in indices are calculated (so, this does not necessarily need to use all of the points in the arrays).

Parameters
pointIndexPoint to build the distances for.
indicesList of indices to compute distances for.
distancesVector to store calculated distances in.
pointSetSizeNumber of points in arrays to calculate distances for.
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
void mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::CreateChildren ( arma::Col< size_t > &  indices,
arma::vec &  distances,
size_t  nearSetSize,
size_t &  farSetSize,
size_t &  usedSetSize 
)
private

Create the children for this node.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
const arma::mat& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Dataset ( ) const
inline

Get a reference to the dataset.

Definition at line 227 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::dataset.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Descendant ( const size_t  index) const

Get the index of a particular descendant point.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::DistanceComps ( ) const
inline
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::DistanceComps ( )
inline
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::FurthestDescendantDistance ( ) const
inline

Get the distance to the furthest descendant.

Definition at line 329 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::furthestDescendantDistance.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::FurthestDescendantDistance ( )
inline

Modify the distance to the furthest descendant.

Definition at line 332 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::furthestDescendantDistance.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
static bool mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::HasSelfChildren ( )
inlinestatic

Returns true: this tree does have self-children.

Definition at line 316 of file cover_tree.hpp.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
bool mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::IsLeaf ( ) const
inline
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::MaxDistance ( const CoverTree< MetricType, RootPointPolicy, StatisticType > *  other) const

Return the maximum distance to another node.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::MaxDistance ( const CoverTree< MetricType, RootPointPolicy, StatisticType > *  other,
const double  distance 
) const

Return the maximum distance to another node given that the point-to-point distance has already been calculated.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::MaxDistance ( const arma::vec &  other) const

Return the maximum distance to another point.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::MaxDistance ( const arma::vec &  other,
const double  distance 
) const

Return the maximum distance to another point given that the distance from the center to the point has already been calculated.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
MetricType& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Metric ( ) const
inline

Get the instantiated metric.

Definition at line 338 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::metric.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::MinDistance ( const CoverTree< MetricType, RootPointPolicy, StatisticType > *  other) const

Return the minimum distance to another node.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::MinDistance ( const CoverTree< MetricType, RootPointPolicy, StatisticType > *  other,
const double  distance 
) const

Return the minimum distance to another node given that the point-to-point distance has already been calculated.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::MinDistance ( const arma::vec &  other) const

Return the minimum distance to another point.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::MinDistance ( const arma::vec &  other,
const double  distance 
) const

Return the minimum distance to another point given that the distance from the center to the point has already been calculated.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
void mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::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 
)
private
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::NumChildren ( ) const
inline

Get the number of children.

Definition at line 243 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::children.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::NumDescendants ( ) const

Get the number of descendant points.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::NumPoints ( ) const
inline

Definition at line 235 of file cover_tree.hpp.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
CoverTree* mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Parent ( ) const
inline

Get the parent node.

Definition at line 319 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::parent.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
CoverTree*& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Parent ( )
inline

Modify the parent node.

Definition at line 321 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::parent.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::ParentDistance ( ) const
inline

Get the distance to the parent.

Definition at line 324 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::parentDistance.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::ParentDistance ( )
inline

Modify the distance to the parent.

Definition at line 326 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::parentDistance.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Point ( ) const
inline

Get the index of the point which this node represents.

Definition at line 230 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::point.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Point ( const size_t  ) const
inline

For compatibility with other trees; the argument is ignored.

Definition at line 232 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::point.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::PruneFarSet ( arma::Col< size_t > &  indices,
arma::vec &  distances,
const double  bound,
const size_t  nearSetSize,
const size_t  pointSetSize 
)
private
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
math::Range mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::RangeDistance ( const CoverTree< MetricType, RootPointPolicy, StatisticType > *  other) const

Return the minimum and maximum distance to another node.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
math::Range mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::RangeDistance ( const CoverTree< MetricType, RootPointPolicy, StatisticType > *  other,
const double  distance 
) const

Return the minimum and maximum distance to another node given that the point-to-point distance has already been calculated.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
math::Range mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::RangeDistance ( const arma::vec &  other) const

Return the minimum and maximum distance to another point.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
math::Range mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::RangeDistance ( const arma::vec &  other,
const double  distance 
) const

Return the minimum and maximum distance to another point given that the point-to-point distance has already been calculated.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
void mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::RemoveNewImplicitNodes ( )
private

Take a look at the last child (the most recently created one) and remove any implicit nodes that have been created.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
int mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Scale ( ) const
inline

Get the scale of this node.

Definition at line 257 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::scale.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
int& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Scale ( )
inline

Modify the scale of this node. Be careful...

Definition at line 259 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::scale.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::SortPointSet ( arma::Col< size_t > &  indices,
arma::vec &  distances,
const size_t  childFarSetSize,
const size_t  childUsedSetSize,
const size_t  farSetSize 
)
private

Assuming that the list of indices and distances is sorted as [ childFarSet | childUsedSet | farSet | usedSet ], resort the sets so the organization is [ childFarSet | farSet | childUsedSet | usedSet ].

The size_t parameters specify the sizes of each set in the array. Only the ordering of the indices and distances arrays will be modified (not their actual contents).

The size of any of the four sets can be zero and this method will handle that case accordingly.

Parameters
indicesList of indices to sort.
distancesList of distances to sort.
childFarSetSizeNumber of points in child far set (childFarSet).
childUsedSetSizeNumber of points in child used set (childUsedSet).
farSetSizeNumber of points in far set (farSet).
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::SplitNearFar ( arma::Col< size_t > &  indices,
arma::vec &  distances,
const double  bound,
const size_t  pointSetSize 
)
private

Split the given indices and distances into a near and a far set, returning the number of points in the near set.

The distances must already be initialized. This will order the indices and distances such that the points in the near set make up the first part of the array and the far set makes up the rest: [ nearSet | farSet ].

Parameters
indicesList of indices; will be reordered.
distancesList of distances; will be reordered.
boundIf the distance is less than or equal to this bound, the point is placed into the near set.
pointSetSizeSize of point set (because we may be sorting a smaller list than the indices vector will hold).
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
const StatisticType& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Stat ( ) const
inline

Get the statistic for this node.

Definition at line 267 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::stat.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
StatisticType& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Stat ( )
inline

Modify the statistic for this node.

Definition at line 269 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::stat.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
std::string mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::ToString ( ) const

Returns a string representation of this object.

Member Data Documentation

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::base
private

The base used to construct the tree.

Definition at line 354 of file cover_tree.hpp.

Referenced by mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Base().

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
std::vector<CoverTree*> mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::children
private
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
const arma::mat& mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::dataset
private
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::distanceComps
private
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::furthestDescendantDistance
private

Distance to the furthest descendant.

Definition at line 369 of file cover_tree.hpp.

Referenced by mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::FurthestDescendantDistance().

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
bool mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::localMetric
private

Whether or not we need to destroy the metric in the destructor.

Definition at line 372 of file cover_tree.hpp.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
MetricType* mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::metric
private

The metric used for this tree.

Definition at line 375 of file cover_tree.hpp.

Referenced by mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Metric().

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::numDescendants
private

The number of descendant points.

Definition at line 360 of file cover_tree.hpp.

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
CoverTree* mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::parent
private

The parent node (NULL if this is the root of the tree).

Definition at line 363 of file cover_tree.hpp.

Referenced by mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Parent().

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
double mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::parentDistance
private

Distance to the parent.

Definition at line 366 of file cover_tree.hpp.

Referenced by mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::ParentDistance().

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
size_t mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::point
private
template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
int mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::scale
private

Scale level of the node.

Definition at line 351 of file cover_tree.hpp.

Referenced by mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Scale().

template<typename MetricType = metric::LMetric<2, true>, typename RootPointPolicy = FirstPointIsRoot, typename StatisticType = EmptyStatistic>
StatisticType mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::stat
private

The instantiated statistic.

Definition at line 357 of file cover_tree.hpp.

Referenced by mlpack::tree::CoverTree< MetricType, RootPointPolicy, StatisticType >::Stat().


The documentation for this class was generated from the following file: