A rectangle type tree tree, such as an R-tree or X-tree. More...

#include <rectangle_tree.hpp>

Classes
class	DualTreeTraverser
	A dual tree traverser for rectangle type trees. More...

class	SingleTreeTraverser
	A single traverser for rectangle type trees. More...

Public Types
typedef MatType	Mat
	So other classes can use TreeType::Mat.

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

typedef AuxiliaryInformationType< RectangleTree >	AuxiliaryInformation
	The auxiliary information type held by the tree.

Public Member Functions
	RectangleTree (const MatType &data, const size_t maxLeafSize=20, const size_t minLeafSize=8, const size_t maxNumChildren=5, const size_t minNumChildren=2, const size_t firstDataIndex=0)
	Construct this as the root node of a rectangle type tree using the given dataset. More...

	RectangleTree (MatType &&data, const size_t maxLeafSize=20, const size_t minLeafSize=8, const size_t maxNumChildren=5, const size_t minNumChildren=2, const size_t firstDataIndex=0)
	Construct this as the root node of a rectangle tree type using the given dataset, and taking ownership of the given dataset. More...

	RectangleTree (RectangleTree *parentNode, const size_t numMaxChildren=0)
	Construct this as an empty node with the specified parent. More...

	RectangleTree (const RectangleTree &other, const bool deepCopy=true, RectangleTree *newParent=NULL)
	Create a rectangle tree by copying the other tree. More...

	RectangleTree (RectangleTree &&other)
	Create a rectangle tree by moving the other tree. More...

RectangleTree &	operator= (const RectangleTree &other)
	Copy the given rectangle tree. More...

RectangleTree &	operator= (RectangleTree &&other)
	Take ownership of the given rectangle tree. More...

template<typename Archive >
	RectangleTree (Archive &ar, const typename std::enable_if_t< cereal::is_loading< Archive >()> *=0)
	Construct the tree from a cereal archive.

	~RectangleTree ()
	Deletes this node, deallocating the memory for the children and calling their destructors in turn. More...

void	SoftDelete ()
	Delete this node of the tree, but leave the stuff contained in it intact. More...

void	NullifyData ()
	Nullify the auxiliary information. More...

void	InsertPoint (const size_t point)
	Inserts a point into the tree. More...

void	InsertPoint (const size_t point, std::vector< bool > &relevels)
	Inserts a point into the tree, tracking which levels have been inserted into. More...

void	InsertNode (RectangleTree *node, const size_t level, std::vector< bool > &relevels)
	Inserts a node into the tree, tracking which levels have been inserted into. More...

bool	DeletePoint (const size_t point)
	Deletes a point from the treeand, updates the bounding rectangle. More...

bool	DeletePoint (const size_t point, std::vector< bool > &relevels)
	Deletes a point from the tree, updates the bounding rectangle, tracking levels. More...

bool	RemoveNode (const RectangleTree *node, std::vector< bool > &relevels)
	Removes a node from the tree. More...

const RectangleTree *	FindByBeginCount (size_t begin, size_t count) const
	Find a node in this tree by its begin and count (const). More...

RectangleTree *	FindByBeginCount (size_t begin, size_t count)
	Find a node in this tree by its begin and count. More...

const bound::HRectBound< MetricType > &	Bound () const
	Return the bound object for this node.

bound::HRectBound< MetricType > &	Bound ()
	Modify the bound object for this node.

const StatisticType &	Stat () const
	Return the statistic object for this node.

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

const AuxiliaryInformationType< RectangleTree > &	AuxiliaryInfo () const
	Return the auxiliary information object of this node.

AuxiliaryInformationType< RectangleTree > &	AuxiliaryInfo ()
	Modify the split object of this node.

bool	IsLeaf () const
	Return whether or not this node is a leaf (true if it has no children).

size_t	MaxLeafSize () const
	Return the maximum leaf size.

size_t &	MaxLeafSize ()
	Modify the maximum leaf size.

size_t	MinLeafSize () const
	Return the minimum leaf size.

size_t &	MinLeafSize ()
	Modify the minimum leaf size.

size_t	MaxNumChildren () const
	Return the maximum number of children (in a non-leaf node).

size_t &	MaxNumChildren ()
	Modify the maximum number of children (in a non-leaf node).

size_t	MinNumChildren () const
	Return the minimum number of children (in a non-leaf node).

size_t &	MinNumChildren ()
	Modify the minimum number of children (in a non-leaf node).

RectangleTree *	Parent () const
	Gets the parent of this node.

RectangleTree *&	Parent ()
	Modify the parent of this node.

const MatType &	Dataset () const
	Get the dataset which the tree is built on.

MatType &	Dataset ()
	Modify the dataset which the tree is built on. Be careful!

MetricType	Metric () const
	Get the metric which the tree uses.

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

size_t	NumChildren () const
	Return the number of child nodes. (One level beneath this one only.)

size_t &	NumChildren ()
	Modify the number of child nodes. Be careful.

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...

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	GetNearestChild (const RectangleTree &queryNode)
	Return the index of the nearest child node to the given query node. More...

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

ElemType	FurthestPointDistance () const
	Return the furthest distance to a point held in this node. More...

ElemType	FurthestDescendantDistance () const
	Return the furthest possible descendant distance. More...

ElemType	MinimumBoundDistance () const
	Return the minimum distance from the center to any edge of the bound. More...

ElemType	ParentDistance () const
	Return the distance from the center of this node to the center of the parent node. More...

ElemType &	ParentDistance ()
	Modify the distance from the center of this node to the center of the parent node. More...

RectangleTree &	Child (const size_t child) const
	Get the specified child. More...

RectangleTree &	Child (const size_t child)
	Modify the specified child. More...

size_t	NumPoints () const
	Return the number of points in this node (returns 0 if this node is not a leaf). More...

size_t	NumDescendants () const
	Return the number of descendants of this node. More...

size_t	Descendant (const size_t index) const
	Return the index (with reference to the dataset) of a particular descendant of this node. More...

size_t	Point (const size_t index) const
	Return the index (with reference to the dataset) of a particular point in this node. More...

size_t &	Point (const size_t index)
	Modify the index of a particular point in this node. More...

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

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

math::RangeType< ElemType >	RangeDistance (const RectangleTree &other) const
	Return the minimum and maximum distance to another node.

template<typename VecType >
ElemType	MinDistance (const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
	Return the minimum distance to another point.

template<typename VecType >
ElemType	MaxDistance (const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
	Return the maximum distance to another point.

template<typename VecType >
math::RangeType< ElemType >	RangeDistance (const VecType &point, typename std::enable_if_t< IsVector< VecType >::value > *=0) const
	Return the minimum and maximum distance to another point.

size_t	TreeSize () const
	Obtains the number of nodes in the tree, starting with this.

size_t	TreeDepth () const
	Obtains the number of levels below this node in the tree, starting with this.

size_t	Begin () const
	Return the index of the beginning point of this subset.

size_t &	Begin ()
	Modify the index of the beginning point of this subset.

size_t	Count () const
	Return the number of points in this subset.

size_t &	Count ()
	Modify the number of points in this subset.

void	CondenseTree (const arma::vec &point, std::vector< bool > &relevels, const bool usePoint)
	Condense the bounding rectangles for this node based on the removal of the point specified by the arma::vec&. More...

bool	ShrinkBoundForPoint (const arma::vec &point)
	Shrink the bound object of this node for the removal of a point. More...

bool	ShrinkBoundForBound (const bound::HRectBound< MetricType > &changedBound)
	Shrink the bound object of this node for the removal of a child node. More...

RectangleTree *	ExactClone ()
	Make an exact copy of this node, pointers and everything.

template<typename Archive >
void	serialize (Archive &ar, const uint32_t)
	Serialize the tree.

Protected Member Functions
	RectangleTree ()
	A default constructor. More...

Protected Attributes
friend	DescentType
	Give friend access for DescentType.

friend	SplitType
	Give friend access for SplitType.

friend	AuxiliaryInformation
	Give friend access for AuxiliaryInformationType.

Friends
class	cereal::access
	Friend access is given for the default constructor.

Detailed Description

template<typename MetricType = metric::EuclideanDistance, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename SplitType = RTreeSplit, typename DescentType = RTreeDescentHeuristic, template< typename > class AuxiliaryInformationType = NoAuxiliaryInformation>
class mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >

A rectangle type tree tree, such as an R-tree or X-tree.

Once the bound and type of dataset is defined, the tree will construct itself. Call the constructor with the dataset to build the tree on, and the entire tree will be built.

This tree does allow growth, so you can add and delete nodes from it.

Template Parameters

MetricType	This must be EuclideanDistance, but the template parameter is required to satisfy the TreeType API.
StatisticType	Extra data contained in the node. See statistic.hpp for the necessary skeleton interface.
MatType	The dataset class.
SplitType	The type of split to use when inserting points.
DescentType	The heuristic to use when descending the tree to insert points.
AuxiliaryInformationType	An auxiliary information contained in the node. This information depends on the type of the RectangleTree.

Constructor & Destructor Documentation

◆ RectangleTree() [1/6]

template<typename MetricType , typename StatisticType , typename MatType, typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::RectangleTree	(	const MatType &	data,
		const size_t	maxLeafSize = `20`,
		const size_t	minLeafSize = `8`,
		const size_t	maxNumChildren = `5`,
		const size_t	minNumChildren = `2`,
		const size_t	firstDataIndex = `0`
	)

Construct this as the root node of a rectangle type tree using the given dataset.

This will modify the ordering of the points in the dataset!

Parameters

data	Dataset from which to create the tree. This will be modified!
maxLeafSize	Maximum size of each leaf in the tree.
minLeafSize	Minimum size of each leaf in the tree.
maxNumChildren	The maximum number of child nodes a non-leaf node may have.
minNumChildren	The minimum number of child nodes a non-leaf node may have.
firstDataIndex	The index of the first data point. UNUSED UNLESS WE ADD SUPPORT FOR HAVING A "CENTERAL" DATA MATRIX.

◆ RectangleTree() [2/6]

template<typename MetricType , typename StatisticType , typename MatType, typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::RectangleTree	(	MatType &&	data,
		const size_t	maxLeafSize = `20`,
		const size_t	minLeafSize = `8`,
		const size_t	maxNumChildren = `5`,
		const size_t	minNumChildren = `2`,
		const size_t	firstDataIndex = `0`
	)

Construct this as the root node of a rectangle tree type using the given dataset, and taking ownership of the given dataset.

Parameters

data	Dataset from which to create the tree.
maxLeafSize	Maximum size of each leaf in the tree.
minLeafSize	Minimum size of each leaf in the tree.
maxNumChildren	The maximum number of child nodes a non-leaf node may have.
minNumChildren	The minimum number of child nodes a non-leaf node may have.
firstDataIndex	The index of the first data point. UNUSED UNLESS WE ADD SUPPORT FOR HAVING A "CENTERAL" DATA MATRIX.

◆ RectangleTree() [3/6]

template<typename MetricType , typename StatisticType , typename MatType, typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::RectangleTree	(	RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType > *	parentNode,
		const size_t	numMaxChildren = `0`
	)

explicit

Construct this as an empty node with the specified parent.

Copying the parameters (maxLeafSize, minLeafSize, maxNumChildren, minNumChildren, firstDataIndex) from the parent.

Parameters

parentNode	The parent of the node that is being constructed.
numMaxChildren	The max number of child nodes (used in x-trees).

◆ RectangleTree() [4/6]

template<typename MetricType , typename StatisticType , typename MatType, typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::RectangleTree	(	const RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType > &	other,
		const bool	deepCopy = `true`,
		RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType > *	newParent = `NULL`
	)

Create a rectangle tree by copying the other tree.

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

Parameters

other	The tree to be copied.
deepCopy	If false, the children are not recursively copied.
newParent	Set a new parent as applicable, default NULL.

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

◆ RectangleTree() [5/6]

template<typename MetricType , typename StatisticType , typename MatType, typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::RectangleTree ( RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType > && other )

Create a rectangle tree by moving the other tree.

Move constructor.

Parameters

other The tree to be moved.

◆ ~RectangleTree()

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::~RectangleTree ( )

Deletes this node, deallocating the memory for the children and calling their destructors in turn.

This will invalidate any younters or references to any nodes which are children of this one.

This will invalidate any pointers or references to any nodes which are children of this one.

◆ RectangleTree() [6/6]

template<typename MetricType , typename StatisticType , typename MatType, typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::RectangleTree ( )

protected

A default constructor.

Default constructor for cereal.

This is meant to only be used with cereal, 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

◆ Child() [1/2]

template<typename MetricType = metric::EuclideanDistance, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename SplitType = RTreeSplit, typename DescentType = RTreeDescentHeuristic, template< typename > class AuxiliaryInformationType = NoAuxiliaryInformation>

RectangleTree& mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::Child ( const size_t child ) const

inline

Get the specified child.

Parameters

child Index of child to return.

◆ Child() [2/2]

template<typename MetricType = metric::EuclideanDistance, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename SplitType = RTreeSplit, typename DescentType = RTreeDescentHeuristic, template< typename > class AuxiliaryInformationType = NoAuxiliaryInformation>

RectangleTree& mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::Child ( const size_t child )

inline

Modify the specified child.

Parameters

child Index of child to return.

◆ CondenseTree()

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

void mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::CondenseTree	(	const arma::vec &	point,
		std::vector< bool > &	relevels,
		const bool	usePoint
	)

Condense the bounding rectangles for this node based on the removal of the point specified by the arma::vec&.

Condense the tree.

This recurses up the tree. If a node goes below the minimum fill, this function will fix the tree.

Parameters

point	The arma::vec& of the point that was removed to require this condesation of the tree.
usePoint	True if we use the optimized version of the algorithm that is possible when we now what point was deleted. False otherwise (eg. if we deleted a node instead of a point).
relevels	The levels that have been reinserted to on this top level insertion.

This shrinks the bounds and moves up the tree if applicable. If a node goes below minimum fill, this code will deal with it.

◆ DeletePoint() [1/2]

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

bool mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::DeletePoint ( const size_t point )

Deletes a point from the treeand, updates the bounding rectangle.

Recurse through the tree to remove the point.

However, the point will be kept in the centeral dataset. (The user may remove it from there if he wants, but he must not change the indices of the other points.) Returns true if the point is successfully removed and false if it is not. (ie. the point is not in the tree)

Once we find the point, we shrink the rectangles if necessary.

◆ DeletePoint() [2/2]

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

bool mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::DeletePoint	(	const size_t	point,
		std::vector< bool > &	relevels
	)

Deletes a point from the tree, updates the bounding rectangle, tracking levels.

Recurse through the tree to remove the point.

However, the point will be kept in the centeral dataset. (The user may remove it from there if he wants, but he must not change the indices of the other points.) Returns true if the point is successfully removed and false if it is not. (ie. the point is not in the tree)

Once we find the point, we shrink the rectangles if necessary.

◆ Descendant()

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

size_t mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::Descendant ( const size_t index ) const

inline

Return the index (with reference to the dataset) of a particular descendant of this node.

Return the index of a particular descendant contained in this node.

The index should be greater than zero but less than the number of descendants.

Parameters

index Index of the descendant.

◆ FindByBeginCount() [1/2]

template<typename MetricType = metric::EuclideanDistance, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename SplitType = RTreeSplit, typename DescentType = RTreeDescentHeuristic, template< typename > class AuxiliaryInformationType = NoAuxiliaryInformation>

const RectangleTree* mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::FindByBeginCount	(	size_t	begin,
		size_t	count
	)		const

Find a node in this tree by its begin and count (const).

Every node is uniquely identified by these two numbers. This is useful for communicating position over the network, when pointers would be invalid.

Parameters

begin	The begin() of the node to find.
count	The count() of the node to find.

Returns: The found node, or NULL if not found.

◆ FindByBeginCount() [2/2]

template<typename MetricType = metric::EuclideanDistance, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename SplitType = RTreeSplit, typename DescentType = RTreeDescentHeuristic, template< typename > class AuxiliaryInformationType = NoAuxiliaryInformation>

RectangleTree* mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::FindByBeginCount	(	size_t	begin,
		size_t	count
	)

Find a node in this tree by its begin and count.

Every node is uniquely identified by these two numbers. This is useful for communicating position over the network, when pointers would be invalid.

Parameters

begin	The begin() of the node to find.
count	The count() of the node to find.

Returns: The found node, or NULL if not found.

◆ FurthestDescendantDistance()

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::ElemType mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::FurthestDescendantDistance ( ) const

inline

Return the furthest possible descendant distance.

This returns the maximum distance from the centroid to the edge of the bound and not the empirical quantity which is the actual furthest descendant distance. So the actual furthest descendant distance may be less than what this method returns (but it will never be greater than this).

◆ FurthestPointDistance()

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::ElemType mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::FurthestPointDistance ( ) const

inline

Return the furthest distance to a point held in this node.

Return a bound on the furthest point in the node form the centroid.

If this is not a leaf node, then the distance is 0 because the node holds no points.

This returns 0 unless the node is a leaf.

◆ GetFurthestChild() [1/2]

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

template<typename VecType >

size_t mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::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).

◆ GetFurthestChild() [2/2]

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

size_t mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::GetFurthestChild ( const RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType > & 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).

◆ GetNearestChild() [1/2]

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

template<typename VecType >

size_t mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::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).

◆ GetNearestChild() [2/2]

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

size_t mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::GetNearestChild ( const RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType > & 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).

◆ InsertNode()

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

void mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::InsertNode	(	RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType > *	node,
		const size_t	level,
		std::vector< bool > &	relevels
	)

Inserts a node into the tree, tracking which levels have been inserted into.

The node will be inserted so that the tree remains valid.

Parameters

node	The node to be inserted.
level	The depth that should match the node where this node is finally inserted. This should be the number returned by calling TreeDepth() from the node that originally contained "node".
relevels	The levels that have been reinserted to on this top level insertion.
node	The node to be inserted.
level	The level on which this node should be inserted.
relevels	The levels that have been reinserted to on this top level insertion.

◆ InsertPoint() [1/2]

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

void mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::InsertPoint ( const size_t point )

Inserts a point into the tree.

Recurse through the tree and insert the point at the leaf node chosen by the heuristic.

Parameters

point The index of a point in the dataset.

◆ InsertPoint() [2/2]

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

void mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::InsertPoint	(	const size_t	point,
		std::vector< bool > &	relevels
	)

Inserts a point into the tree, tracking which levels have been inserted into.

Parameters

point	The index of a point in the dataset.
relevels	The levels that have been reinserted to on this top level insertion.

◆ MinimumBoundDistance()

template<typename MetricType = metric::EuclideanDistance, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename SplitType = RTreeSplit, typename DescentType = RTreeDescentHeuristic, template< typename > class AuxiliaryInformationType = NoAuxiliaryInformation>

ElemType mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::MinimumBoundDistance ( ) const

inline

Return the minimum distance from the center to any edge of the bound.

Currently, this returns 0, which doesn't break algorithms, but it isn't necessarily correct, either.

◆ NullifyData()

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

void mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::NullifyData ( )

Nullify the auxiliary information.

Used for memory management. Be cafeful.

◆ NumDescendants()

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

size_t mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::NumDescendants ( ) const

inline

Return the number of descendants of this node.

Return the number of descendants under or in this node.

For a non-leaf in a binary space tree, this is the number of points at the descendant leaves. For a leaf, this is the number of points in the leaf.

◆ NumPoints()

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

size_t mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::NumPoints ( ) const

inline

Return the number of points in this node (returns 0 if this node is not a leaf).

Return the number of points contained in this node.

Zero if it is a non-leaf node.

◆ operator=() [1/2]

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType > & mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::operator= ( const RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType > & other )

Copy the given rectangle tree.

Copy assignment operator: copy the given other tree.

Parameters

other The tree to be copied.

◆ operator=() [2/2]

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType > & mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::operator= ( RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType > && other )

Take ownership of the given rectangle tree.

Move assignment operator: take ownership of the given tree.

Parameters

other The tree to take ownership of.

◆ ParentDistance() [1/2]

template<typename MetricType = metric::EuclideanDistance, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename SplitType = RTreeSplit, typename DescentType = RTreeDescentHeuristic, template< typename > class AuxiliaryInformationType = NoAuxiliaryInformation>

ElemType mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::ParentDistance ( ) const

inline

Return the distance from the center of this node to the center of the parent node.

◆ ParentDistance() [2/2]

template<typename MetricType = metric::EuclideanDistance, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename SplitType = RTreeSplit, typename DescentType = RTreeDescentHeuristic, template< typename > class AuxiliaryInformationType = NoAuxiliaryInformation>

ElemType& mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::ParentDistance ( )

inline

Modify the distance from the center of this node to the center of the parent node.

◆ Point() [1/2]

template<typename MetricType = metric::EuclideanDistance, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename SplitType = RTreeSplit, typename DescentType = RTreeDescentHeuristic, template< typename > class AuxiliaryInformationType = NoAuxiliaryInformation>

size_t mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::Point ( const size_t index ) const

inline

Return the index (with reference to the dataset) of a particular point in this node.

This will happily return invalid indices if the given index is greater than the number of points in this node (obtained with NumPoints()) – be careful.

Parameters

index Index of point for which a dataset index is wanted.

◆ Point() [2/2]

template<typename MetricType = metric::EuclideanDistance, typename StatisticType = EmptyStatistic, typename MatType = arma::mat, typename SplitType = RTreeSplit, typename DescentType = RTreeDescentHeuristic, template< typename > class AuxiliaryInformationType = NoAuxiliaryInformation>

size_t& mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::Point ( const size_t index )

inline

Modify the index of a particular point in this node.

Be very careful when you do this! You may make the tree invalid.

◆ RemoveNode()

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

bool mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::RemoveNode	(	const RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType > *	node,
		std::vector< bool > &	relevels
	)

Removes a node from the tree.

Recurse through the tree to remove the node.

You are responsible for deleting it if you wish to do so.

Once we find the node, we shrink the rectangles if necessary.

◆ ShrinkBoundForBound()

template<typename MetricType, typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

bool mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::ShrinkBoundForBound ( const bound::HRectBound< MetricType > & changedBound )

Shrink the bound object of this node for the removal of a child node.

Shrink the bound so it fits tightly after the removal of another bound.

Parameters

changedBound The HRectBound<>& of the bound that was removed to reqire this shrinking.

Returns: true if the bound needed to be changed, false if it did not.

◆ ShrinkBoundForPoint()

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

bool mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::ShrinkBoundForPoint ( const arma::vec & point )

Shrink the bound object of this node for the removal of a point.

Shrink the bound so it fits tightly after the removal of this point.

Parameters

point The arma::vec& of the point that was removed to require this shrinking.

Returns: true if the bound needed to be changed, false if it did not.

◆ SoftDelete()

template<typename MetricType , typename StatisticType , typename MatType , typename SplitType , typename DescentType , template< typename > class AuxiliaryInformationType>

void mlpack::tree::RectangleTree< MetricType, StatisticType, MatType, SplitType, DescentType, AuxiliaryInformationType >::SoftDelete ( )

Delete this node of the tree, but leave the stuff contained in it intact.

Deletes this node but leaves the children untouched.

This is used when splitting a node, where the data in this tree is moved to two other trees.

Needed for when we split nodes and remove nodes (inserting and deleting points).

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

src/mlpack/core/tree/rectangle_tree/rectangle_tree.hpp
src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ RectangleTree() [1/6]

◆ RectangleTree() [2/6]

◆ RectangleTree() [3/6]

◆ RectangleTree() [4/6]

◆ RectangleTree() [5/6]

◆ ~RectangleTree()

◆ RectangleTree() [6/6]

Member Function Documentation

◆ Child() [1/2]

◆ Child() [2/2]

◆ CondenseTree()

◆ DeletePoint() [1/2]

◆ DeletePoint() [2/2]

◆ Descendant()

◆ FindByBeginCount() [1/2]

◆ FindByBeginCount() [2/2]

◆ FurthestDescendantDistance()

◆ FurthestPointDistance()

◆ GetFurthestChild() [1/2]

◆ GetFurthestChild() [2/2]

◆ GetNearestChild() [1/2]

◆ GetNearestChild() [2/2]

◆ InsertNode()

◆ InsertPoint() [1/2]

◆ InsertPoint() [2/2]

◆ MinimumBoundDistance()

◆ NullifyData()

◆ NumDescendants()

◆ NumPoints()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ ParentDistance() [1/2]

◆ ParentDistance() [2/2]

◆ Point() [1/2]

◆ Point() [2/2]

◆ RemoveNode()

◆ ShrinkBoundForBound()

◆ ShrinkBoundForPoint()

◆ SoftDelete()