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

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
template<typename RuleType >
using	BreadthFirstDualTreeTraverser = DualTreeTraverser< RuleType >

typedef MatType::elem_type	ElemType
	The type held by the matrix type. More...

typedef MatType	Mat
	So that other classes can access the matrix type. More...

Public Member Functions
	CoverTree (const MatType &dataset, const ElemType base=2.0, MetricType *metric=NULL)
	Create the cover tree with the given dataset and given base. More...

	CoverTree (const MatType &dataset, MetricType &metric, const ElemType base=2.0)
	Create the cover tree with the given dataset and the given instantiated metric. More...

	CoverTree (MatType &&dataset, const ElemType base=2.0)
	Create the cover tree with the given dataset, taking ownership of the dataset. More...

	CoverTree (MatType &&dataset, MetricType &metric, const ElemType base=2.0)
	Create the cover tree with the given dataset and the given instantiated metric, taking ownership of the dataset. More...

	CoverTree (const MatType &dataset, const ElemType base, const size_t pointIndex, const int scale, CoverTree *parent, const ElemType 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 MatType &dataset, const ElemType base, const size_t pointIndex, const int scale, CoverTree parent, const ElemType parentDistance, const ElemType 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 (CoverTree &&other)
	Move constructor for a Cover Tree, possess all the members of the given tree. More...

template<typename Archive >
	CoverTree (Archive &ar, const typename std::enable_if_t< Archive::is_loading::value > *=0)
	Create a cover tree from a boost::serialization archive. More...

	~CoverTree ()
	Delete this cover tree node and its children. More...

ElemType	Base () const
	Get the base. More...

ElemType &	Base ()
	Modify the base; don't do this, you'll break everything. More...

void	Center (arma::vec &center) const
	Get the center of the node and store it in the given vector. More...

const CoverTree &	Child (const size_t index) const
	Get a particular child node. More...

CoverTree &	Child (const size_t index)
	Modify a particular child node. More...

CoverTree *&	ChildPtr (const size_t index)

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 MatType &	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 ()

ElemType	FurthestDescendantDistance () const
	Get the distance from the center of the node to the furthest descendant. More...

ElemType &	FurthestDescendantDistance ()
	Modify the distance from the center of the node to the furthest descendant. More...

ElemType	FurthestPointDistance () const
	Get the distance to the furthest point. This is always 0 for cover trees. More...

template<typename VecType >
size_t	GetFurthestChild (const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0)
	Return the index of the furthest child node to the given query point. More...

size_t	GetFurthestChild (const CoverTree &queryNode)
	Return the index of the furthest child node to the given query node. More...

template<typename VecType >
size_t	GetNearestChild (const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0)
	Return the index of the nearest child node to the given query point. More...

size_t	GetNearestChild (const CoverTree &queryNode)
	Return the index of the nearest child node to the given query node. More...

bool	IsLeaf () const

ElemType	MaxDistance (const CoverTree &other) const
	Return the maximum distance to another node. More...

ElemType	MaxDistance (const CoverTree &other, const ElemType distance) const
	Return the maximum distance to another node given that the point-to-point distance has already been calculated. More...

ElemType	MaxDistance (const arma::vec &other) const
	Return the maximum distance to another point. More...

ElemType	MaxDistance (const arma::vec &other, const ElemType 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...

ElemType	MinDistance (const CoverTree &other) const
	Return the minimum distance to another node. More...

ElemType	MinDistance (const CoverTree &other, const ElemType distance) const
	Return the minimum distance to another node given that the point-to-point distance has already been calculated. More...

ElemType	MinDistance (const arma::vec &other) const
	Return the minimum distance to another point. More...

ElemType	MinDistance (const arma::vec &other, const ElemType distance) const
	Return the minimum distance to another point given that the distance from the center to the point has already been calculated. More...

ElemType	MinimumBoundDistance () const
	Get the minimum distance from the center to any bound edge (this is the same as furthestDescendantDistance). 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

CoverTree *	Parent () const
	Get the parent node. More...

CoverTree *&	Parent ()
	Modify the parent node. More...

ElemType	ParentDistance () const
	Get the distance to the parent. More...

ElemType &	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::RangeType< ElemType >	RangeDistance (const CoverTree &other) const
	Return the minimum and maximum distance to another node. More...

math::RangeType< ElemType >	RangeDistance (const CoverTree &other, const ElemType distance) const
	Return the minimum and maximum distance to another node given that the point-to-point distance has already been calculated. More...

math::RangeType< ElemType >	RangeDistance (const arma::vec &other) const
	Return the minimum and maximum distance to another point. More...

math::RangeType< ElemType >	RangeDistance (const arma::vec &other, const ElemType 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...

template<typename Archive >
void	Serialize (Archive &ar, const unsigned int)
	Serialize the tree. More...

const StatisticType &	Stat () const
	Get the statistic for this node. More...

StatisticType &	Stat ()
	Modify the statistic for this node. More...

Protected Member Functions
	CoverTree ()
	A default constructor. 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 ElemType 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 ElemType 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
ElemType	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 MatType *	dataset
	Reference to the matrix which this tree is built on. More...

size_t	distanceComps

ElemType	furthestDescendantDistance
	Distance to the furthest descendant. More...

bool	localDataset
	If true, we own the dataset and need to destroy it in the destructor. 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...

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

ElemType	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 StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>
class mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >

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 two invariants:

nesting: the level C_i is a subset of the level C_{i - 1}.
covering: all node in level C_{i - 1} have at least one node in the level C_i with distance less than or equal to b^i (exactly one of these is a parent of the point in level C_{i - 1}.

Note that in the cover tree paper, there is a third invariant (the 'separation invariant'), but that does not apply to our implementation, because we have relaxed the invariant.

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

MetricType	Metric type to use during tree construction.
RootPointPolicy	Determines which point to use as the root node.
StatisticType	Statistic to be used during tree creation.
MatType	Type of matrix to build the tree on (generally mat or sp_mat).

Definition at line 99 of file cover_tree.hpp.

Member Typedef Documentation

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

template<typename RuleType >

using mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::BreadthFirstDualTreeTraverser = DualTreeTraverser<RuleType>

Definition at line 264 of file cover_tree.hpp.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

typedef MatType::elem_type mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::ElemType

The type held by the matrix type.

Definition at line 105 of file cover_tree.hpp.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

typedef MatType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Mat

So that other classes can access the matrix type.

Definition at line 103 of file cover_tree.hpp.

Constructor & Destructor Documentation

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::CoverTree	(	const MatType &	dataset,
		const ElemType	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

dataset	Reference to the dataset to build a tree on.
base	Base to use during tree building (default 2.0).

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::CoverTree	(	const MatType &	dataset,
		MetricType &	metric,
		const ElemType	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

dataset	Reference to the dataset to build a tree on.
metric	Instantiated metric to use during tree building.
base	Base to use during tree building (default 2.0).

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::CoverTree	(	MatType &&	dataset,
		const ElemType	base = `2.0`
	)

Create the cover tree with the given dataset, taking ownership of the dataset.

Optionally, set the base.

Parameters

dataset	Reference to the dataset to build a tree on.
base	Base to use during tree building (default 2.0).

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::CoverTree	(	MatType &&	dataset,
		MetricType &	metric,
		const ElemType	base = `2.0`
	)

Create the cover tree with the given dataset and the given instantiated metric, taking ownership of the dataset.

Optionally, set the base.

Parameters

dataset	Reference to the dataset to build a tree on.
metric	Instantiated metric to use during tree building.
base	Base to use during tree building (default 2.0).

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::CoverTree	(	const MatType &	dataset,
		const ElemType	base,
		const size_t	pointIndex,
		const int	scale,
		CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > *	parent,
		const ElemType	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

dataset	Reference to the dataset to build a tree on.
base	Base to use during tree building.
pointIndex	Index of the point this node references.
scale	Scale of this level in the tree.
parent	Parent of this node (NULL indicates no parent).
parentDistance	Distance to the parent node.
indices	Array of indices, ordered [ nearSet \| farSet \| usedSet ]; will be modified to [ farSet \| usedSet ].
distances	Array 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.
nearSetSize	Size of the near set; if 0, this will be a leaf.
farSetSize	Size of the far set; may be modified (if this node uses any points in the far set).
usedSetSize	The number of points used will be added to this number.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::CoverTree	(	const MatType &	dataset,
		const ElemType	base,
		const size_t	pointIndex,
		const int	scale,
		CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > *	parent,
		const ElemType	parentDistance,
		const ElemType	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

dataset	Reference to the dataset this node is a part of.
base	Base that was used for tree building.
pointIndex	Index of the point in the dataset which this node refers to.
scale	Scale of this node's level in the tree.
parent	Parent node (NULL indicates no parent).
parentDistance	Distance to parent node point.
furthestDescendantDistance	Distance to furthest descendant point.
metric	Instantiated metric (optional).

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::CoverTree ( const CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > & other )

Create a cover tree from another tree.

Be careful! This may use a lot of memory and take a lot of time. This will also make a copy of the dataset.

Parameters

other Cover tree to copy from.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::CoverTree ( CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > && other )

Move constructor for a Cover Tree, possess all the members of the given tree.

Parameters

other Cover Tree to move.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

template<typename Archive >

mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::CoverTree	(	Archive &	ar,
		const typename std::enable_if_t< Archive::is_loading::value > *	= `0`
	)

Create a cover tree from a boost::serialization archive.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::~CoverTree ( )

Delete this cover tree node and its children.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::CoverTree ( )

protected

A default constructor.

This is meant to only be used with boost::serialization, which is allowed with the friend declaration below. This does not return a valid tree! This method must be protected, so that the serialization shim can work with the default constructor.

Member Function Documentation

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Base ( ) const

inline

Get the base.

Definition at line 304 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Base ( )

inline

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

Definition at line 306 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

void mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Center ( arma::vec & center ) const

inline

Get the center of the node and store it in the given vector.

Definition at line 412 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

const CoverTree& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Child ( const size_t index ) const

inline

Get a particular child node.

Definition at line 278 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

CoverTree& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Child ( const size_t index )

inline

Modify a particular child node.

Definition at line 280 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

CoverTree*& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::ChildPtr ( const size_t index )

inline

Definition at line 282 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

const std::vector<CoverTree*>& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Children ( ) const

inline

Get the children.

Definition at line 288 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

std::vector<CoverTree*>& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Children ( )

inline

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

Definition at line 290 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::children, mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Descendant(), and mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::NumDescendants().

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

void mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::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

pointIndex	Point to build the distances for.
indices	List of indices to compute distances for.
distances	Vector to store calculated distances in.
pointSetSize	Number of points in arrays to calculate distances for.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

void mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::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 StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

const MatType& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Dataset ( ) const

inline

Get a reference to the dataset.

Definition at line 267 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Descendant ( const size_t index ) const

Get the index of a particular descendant point.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::DistanceComps ( ) const

inline

Definition at line 555 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::DistanceComps ( )

inline

Definition at line 556 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::FurthestDescendantDistance ( ) const

inline

Get the distance from the center of the node to the furthest descendant.

Definition at line 401 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::FurthestDescendantDistance ( )

inline

Modify the distance from the center of the node to the furthest descendant.

Definition at line 405 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::FurthestPointDistance ( ) const

inline

Get the distance to the furthest point. This is always 0 for cover trees.

Definition at line 398 of file cover_tree.hpp.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

template<typename VecType >

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::GetFurthestChild	(	const VecType &	point,
		typename std::enable_if_t< IsVector< VecType >::value > *	= `0`
	)

Return the index of the furthest child node to the given query point.

If this is a leaf node, it will return NumChildren() (invalid index).

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::GetFurthestChild ( const CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > & queryNode )

Return the index of the furthest child node to the given query node.

If it can't decide, it will return NumChildren() (invalid index).

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

template<typename VecType >

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::GetNearestChild	(	const VecType &	point,
		typename std::enable_if_t< IsVector< VecType >::value > *	= `0`
	)

Return the index of the nearest child node to the given query point.

If this is a leaf node, it will return NumChildren() (invalid index).

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::GetNearestChild ( const CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > & queryNode )

Return the index of the nearest child node to the given query node.

If it can't decide, it will return NumChildren() (invalid index).

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

bool mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::IsLeaf ( ) const

inline

Definition at line 274 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::MaxDistance ( const CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > & other ) const

Return the maximum distance to another node.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::MaxDistance	(	const CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > &	other,
		const ElemType	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 StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::MaxDistance ( const arma::vec & other ) const

Return the maximum distance to another point.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::MaxDistance	(	const arma::vec &	other,
		const ElemType	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 StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

MetricType& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Metric ( ) const

inline

Get the instantiated metric.

Definition at line 418 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::MinDistance ( const CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > & other ) const

Return the minimum distance to another node.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::MinDistance	(	const CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > &	other,
		const ElemType	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 StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::MinDistance ( const arma::vec & other ) const

Return the minimum distance to another point.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::MinDistance	(	const arma::vec &	other,
		const ElemType	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 StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::MinimumBoundDistance ( ) const

inline

Get the minimum distance from the center to any bound edge (this is the same as furthestDescendantDistance).

Definition at line 409 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

void mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::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 StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::NumChildren ( ) const

inline

Get the number of children.

Definition at line 285 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::NumDescendants ( ) const

Get the number of descendant points.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::NumPoints ( ) const

inline

Definition at line 275 of file cover_tree.hpp.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

CoverTree* mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Parent ( ) const

inline

Get the parent node.

Definition at line 388 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

CoverTree*& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Parent ( )

inline

Modify the parent node.

Definition at line 390 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::ParentDistance ( ) const

inline

Get the distance to the parent.

Definition at line 393 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::ParentDistance ( )

inline

Modify the distance to the parent.

Definition at line 395 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Point ( ) const

inline

Get the index of the point which this node represents.

Definition at line 270 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Point ( const size_t ) const

inline

For compatibility with other trees; the argument is ignored.

Definition at line 272 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::PruneFarSet	(	arma::Col< size_t > &	indices,
		arma::vec &	distances,
		const ElemType	bound,
		const size_t	nearSetSize,
		const size_t	pointSetSize
	)

private

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

math::RangeType<ElemType> mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::RangeDistance ( const CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > & other ) const

Return the minimum and maximum distance to another node.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

math::RangeType<ElemType> mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::RangeDistance	(	const CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > &	other,
		const ElemType	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 StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

math::RangeType<ElemType> mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::RangeDistance ( const arma::vec & other ) const

Return the minimum and maximum distance to another point.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

math::RangeType<ElemType> mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::RangeDistance	(	const arma::vec &	other,
		const ElemType	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 StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

void mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::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 StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

int mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Scale ( ) const

inline

Get the scale of this node.

Definition at line 299 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

int& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Scale ( )

inline

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

Definition at line 301 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

template<typename Archive >

void mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Serialize	(	Archive &	ar,
		const unsigned	int
	)

Serialize the tree.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::SortPointSet	(	arma::Col< size_t > &	indices,
		arma::vec &	distances,
		const size_t	childFarSetSize,
		const size_t	childUsedSetSize,
		const size_t	farSetSize
	)

private

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

indices	List of indices to sort.
distances	List of distances to sort.
childFarSetSize	Number of points in child far set (childFarSet).
childUsedSetSize	Number of points in child used set (childUsedSet).
farSetSize	Number of points in far set (farSet).

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::SplitNearFar	(	arma::Col< size_t > &	indices,
		arma::vec &	distances,
		const ElemType	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

indices	List of indices; will be reordered.
distances	List of distances; will be reordered.
bound	If the distance is less than or equal to this bound, the point is placed into the near set.
pointSetSize	Size 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 StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

const StatisticType& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Stat ( ) const

inline

Get the statistic for this node.

Definition at line 309 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

StatisticType& mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Stat ( )

inline

Modify the statistic for this node.

Definition at line 311 of file cover_tree.hpp.

References mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::GetFurthestChild(), mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::GetNearestChild(), mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::MaxDistance(), mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::MinDistance(), mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::point, mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::RangeDistance(), and mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::stat.

Member Data Documentation

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::base

private

The base used to construct the tree.

Definition at line 430 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

std::vector<CoverTree*> mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::children

private

The list of children; the first is the self-child.

Definition at line 426 of file cover_tree.hpp.

Referenced by mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Child(), mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::ChildPtr(), mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Children(), mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::IsLeaf(), and mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::NumChildren().

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

const MatType* mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::dataset

private

Reference to the matrix which this tree is built on.

Definition at line 422 of file cover_tree.hpp.

Referenced by mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Center(), and mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::Dataset().

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::distanceComps

private

Definition at line 559 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::furthestDescendantDistance

private

Distance to the furthest descendant.

Definition at line 440 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

bool mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::localDataset

private

If true, we own the dataset and need to destroy it in the destructor.

Definition at line 444 of file cover_tree.hpp.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

bool mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::localMetric

private

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

Definition at line 442 of file cover_tree.hpp.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

MetricType* mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::metric

private

The metric used for this tree.

Definition at line 446 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::numDescendants

private

The number of descendant points.

Definition at line 434 of file cover_tree.hpp.

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

CoverTree* mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::parent

private

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

Definition at line 436 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

ElemType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::parentDistance

private

Distance to the parent.

Definition at line 438 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

size_t mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::point

private

Index of the point in the matrix which this node represents.

Definition at line 424 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

int mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::scale

private

Scale level of the node.

Definition at line 428 of file cover_tree.hpp.

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

template<typename MetricType = metric::LMetric<2, true>, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename RootPointPolicy = FirstPointIsRoot>

StatisticType mlpack::tree::CoverTree< MetricType, StatisticType, MatType, RootPointPolicy >::stat

private

The instantiated statistic.

Definition at line 432 of file cover_tree.hpp.

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

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

src/mlpack/core/tree/cover_tree/cover_tree.hpp

Classes

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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