\section{mlpack\+:\+:tree Namespace Reference}
\label{namespacemlpack_1_1tree}\index{mlpack\+::tree@{mlpack\+::tree}}


Trees and tree-\/building procedures.  


\subsection*{Namespaces}
\begin{DoxyCompactItemize}
\item 
 \textbf{ enumerate}
\item 
 \textbf{ split}
\end{DoxyCompactItemize}
\subsection*{Classes}
\begin{DoxyCompactItemize}
\item 
class \textbf{ All\+Categorical\+Split}
\begin{DoxyCompactList}\small\item\em The \doxyref{All\+Categorical\+Split}{p.}{classmlpack_1_1tree_1_1AllCategoricalSplit} is a splitting function that will split categorical features into many children\+: one child for each category. \end{DoxyCompactList}\item 
class \textbf{ All\+Dimension\+Select}
\begin{DoxyCompactList}\small\item\em This dimension selection policy allows any dimension to be selected for splitting. \end{DoxyCompactList}\item 
class \textbf{ Axis\+Parallel\+Proj\+Vector}
\begin{DoxyCompactList}\small\item\em \doxyref{Axis\+Parallel\+Proj\+Vector}{p.}{classmlpack_1_1tree_1_1AxisParallelProjVector} defines an axis-\/parallel projection vector. \end{DoxyCompactList}\item 
class \textbf{ Best\+Binary\+Numeric\+Split}
\begin{DoxyCompactList}\small\item\em The \doxyref{Best\+Binary\+Numeric\+Split}{p.}{classmlpack_1_1tree_1_1BestBinaryNumericSplit} is a splitting function for decision trees that will exhaustively search a numeric dimension for the best binary split. \end{DoxyCompactList}\item 
class \textbf{ Binary\+Numeric\+Split}
\begin{DoxyCompactList}\small\item\em The \doxyref{Binary\+Numeric\+Split}{p.}{classmlpack_1_1tree_1_1BinaryNumericSplit} class implements the numeric feature splitting strategy devised by Gama, Rocha, and Medas in the following paper\+: \end{DoxyCompactList}\item 
class \textbf{ Binary\+Numeric\+Split\+Info}
\item 
class \textbf{ Binary\+Space\+Tree}
\begin{DoxyCompactList}\small\item\em A binary space partitioning tree, such as a K\+D-\/tree or a ball tree. \end{DoxyCompactList}\item 
class \textbf{ Categorical\+Split\+Info}
\item 
class \textbf{ Compare\+Cosine\+Node}
\item 
class \textbf{ Cosine\+Tree}
\item 
class \textbf{ Cover\+Tree}
\begin{DoxyCompactList}\small\item\em A cover tree is a tree specifically designed to speed up nearest-\/neighbor computation in high-\/dimensional spaces. \end{DoxyCompactList}\item 
class \textbf{ Decision\+Tree}
\begin{DoxyCompactList}\small\item\em This class implements a generic decision tree learner. \end{DoxyCompactList}\item 
class \textbf{ Discrete\+Hilbert\+Value}
\begin{DoxyCompactList}\small\item\em The \doxyref{Discrete\+Hilbert\+Value}{p.}{classmlpack_1_1tree_1_1DiscreteHilbertValue} class stores Hilbert values for all of the points in a \doxyref{Rectangle\+Tree}{p.}{classmlpack_1_1tree_1_1RectangleTree} node, and calculates Hilbert values for new points. \end{DoxyCompactList}\item 
class \textbf{ Empty\+Statistic}
\begin{DoxyCompactList}\small\item\em Empty statistic if you are not interested in storing statistics in your tree. \end{DoxyCompactList}\item 
class \textbf{ Example\+Tree}
\begin{DoxyCompactList}\small\item\em This is not an actual space tree but instead an example tree that exists to show and document all the functions that mlpack trees must implement. \end{DoxyCompactList}\item 
class \textbf{ First\+Point\+Is\+Root}
\begin{DoxyCompactList}\small\item\em This class is meant to be used as a choice for the policy class Root\+Point\+Policy of the \doxyref{Cover\+Tree}{p.}{classmlpack_1_1tree_1_1CoverTree} class. \end{DoxyCompactList}\item 
class \textbf{ Gini\+Gain}
\begin{DoxyCompactList}\small\item\em The Gini gain, a measure of set purity usable as a fitness function (Fitness\+Function) for decision trees. \end{DoxyCompactList}\item 
class \textbf{ Gini\+Impurity}
\item 
class \textbf{ Greedy\+Single\+Tree\+Traverser}
\item 
class \textbf{ Hilbert\+R\+Tree\+Auxiliary\+Information}
\item 
class \textbf{ Hilbert\+R\+Tree\+Descent\+Heuristic}
\begin{DoxyCompactList}\small\item\em This class chooses the best child of a node in a Hilbert R tree when inserting a new point. \end{DoxyCompactList}\item 
class \textbf{ Hilbert\+R\+Tree\+Split}
\begin{DoxyCompactList}\small\item\em The splitting procedure for the Hilbert R tree. \end{DoxyCompactList}\item 
class \textbf{ Hoeffding\+Categorical\+Split}
\begin{DoxyCompactList}\small\item\em This is the standard Hoeffding-\/bound categorical feature proposed in the paper below\+: \end{DoxyCompactList}\item 
class \textbf{ Hoeffding\+Numeric\+Split}
\begin{DoxyCompactList}\small\item\em The \doxyref{Hoeffding\+Numeric\+Split}{p.}{classmlpack_1_1tree_1_1HoeffdingNumericSplit} class implements the numeric feature splitting strategy alluded to by Domingos and Hulten in the following paper\+: \end{DoxyCompactList}\item 
class \textbf{ Hoeffding\+Tree}
\begin{DoxyCompactList}\small\item\em The \doxyref{Hoeffding\+Tree}{p.}{classmlpack_1_1tree_1_1HoeffdingTree} object represents all of the necessary information for a Hoeffding-\/bound-\/based decision tree. \end{DoxyCompactList}\item 
class \textbf{ Hoeffding\+Tree\+Model}
\begin{DoxyCompactList}\small\item\em This class is a serializable Hoeffding tree model that can hold four different types of Hoeffding trees. \end{DoxyCompactList}\item 
class \textbf{ Hyperplane\+Base}
\begin{DoxyCompactList}\small\item\em \doxyref{Hyperplane\+Base}{p.}{classmlpack_1_1tree_1_1HyperplaneBase} defines a splitting hyperplane based on a projection vector and projection value. \end{DoxyCompactList}\item 
class \textbf{ Information\+Gain}
\begin{DoxyCompactList}\small\item\em The standard information gain criterion, used for calculating gain in decision trees. \end{DoxyCompactList}\item 
struct \textbf{ Is\+Spill\+Tree}
\item 
struct \textbf{ Is\+Spill\+Tree$<$ tree\+::\+Spill\+Tree$<$ Metric\+Type, Statistic\+Type, Mat\+Type, Hyperplane\+Type, Split\+Type $>$ $>$}
\item 
class \textbf{ Mean\+Space\+Split}
\item 
class \textbf{ Mean\+Split}
\begin{DoxyCompactList}\small\item\em A binary space partitioning tree node is split into its left and right child. \end{DoxyCompactList}\item 
class \textbf{ Midpoint\+Space\+Split}
\item 
class \textbf{ Midpoint\+Split}
\begin{DoxyCompactList}\small\item\em A binary space partitioning tree node is split into its left and right child. \end{DoxyCompactList}\item 
class \textbf{ Minimal\+Coverage\+Sweep}
\begin{DoxyCompactList}\small\item\em The \doxyref{Minimal\+Coverage\+Sweep}{p.}{classmlpack_1_1tree_1_1MinimalCoverageSweep} class finds a partition along which we can split a node according to the coverage of two resulting nodes. \end{DoxyCompactList}\item 
class \textbf{ Minimal\+Splits\+Number\+Sweep}
\begin{DoxyCompactList}\small\item\em The \doxyref{Minimal\+Splits\+Number\+Sweep}{p.}{classmlpack_1_1tree_1_1MinimalSplitsNumberSweep} class finds a partition along which we can split a node according to the number of required splits of the node. \end{DoxyCompactList}\item 
class \textbf{ Multiple\+Random\+Dimension\+Select}
\begin{DoxyCompactList}\small\item\em This dimension selection policy allows the selection from a few random dimensions. \end{DoxyCompactList}\item 
class \textbf{ No\+Auxiliary\+Information}
\item 
class \textbf{ Numeric\+Split\+Info}
\item 
class \textbf{ Octree}
\item 
class \textbf{ Proj\+Vector}
\begin{DoxyCompactList}\small\item\em \doxyref{Proj\+Vector}{p.}{classmlpack_1_1tree_1_1ProjVector} defines a general projection vector (not necessarily axis-\/parallel). \end{DoxyCompactList}\item 
struct \textbf{ Queue\+Frame}
\item 
class \textbf{ Random\+Dimension\+Select}
\begin{DoxyCompactList}\small\item\em This dimension selection policy only selects one single random dimension. \end{DoxyCompactList}\item 
class \textbf{ Random\+Forest}
\item 
class \textbf{ Rectangle\+Tree}
\begin{DoxyCompactList}\small\item\em A rectangle type tree tree, such as an R-\/tree or X-\/tree. \end{DoxyCompactList}\item 
class \textbf{ R\+Plus\+Plus\+Tree\+Auxiliary\+Information}
\item 
class \textbf{ R\+Plus\+Plus\+Tree\+Descent\+Heuristic}
\item 
class \textbf{ R\+Plus\+Plus\+Tree\+Split\+Policy}
\begin{DoxyCompactList}\small\item\em The \doxyref{R\+Plus\+Plus\+Tree\+Split\+Policy}{p.}{classmlpack_1_1tree_1_1RPlusPlusTreeSplitPolicy} helps to determine the subtree into which we should insert a child of an intermediate node that is being split. \end{DoxyCompactList}\item 
class \textbf{ R\+Plus\+Tree\+Descent\+Heuristic}
\item 
class \textbf{ R\+Plus\+Tree\+Split}
\begin{DoxyCompactList}\small\item\em The \doxyref{R\+Plus\+Tree\+Split}{p.}{classmlpack_1_1tree_1_1RPlusTreeSplit} class performs the split process of a node on overflow. \end{DoxyCompactList}\item 
class \textbf{ R\+Plus\+Tree\+Split\+Policy}
\begin{DoxyCompactList}\small\item\em The \doxyref{R\+Plus\+Plus\+Tree\+Split\+Policy}{p.}{classmlpack_1_1tree_1_1RPlusPlusTreeSplitPolicy} helps to determine the subtree into which we should insert a child of an intermediate node that is being split. \end{DoxyCompactList}\item 
class \textbf{ R\+P\+Tree\+Max\+Split}
\begin{DoxyCompactList}\small\item\em This class splits a node by a random hyperplane. \end{DoxyCompactList}\item 
class \textbf{ R\+P\+Tree\+Mean\+Split}
\begin{DoxyCompactList}\small\item\em This class splits a binary space tree. \end{DoxyCompactList}\item 
class \textbf{ R\+Star\+Tree\+Descent\+Heuristic}
\begin{DoxyCompactList}\small\item\em When descending a \doxyref{Rectangle\+Tree}{p.}{classmlpack_1_1tree_1_1RectangleTree} to insert a point, we need to have a way to choose a child node when the point isn\textquotesingle{}t enclosed by any of them. \end{DoxyCompactList}\item 
class \textbf{ R\+Star\+Tree\+Split}
\begin{DoxyCompactList}\small\item\em A Rectangle Tree has new points inserted at the bottom. \end{DoxyCompactList}\item 
class \textbf{ R\+Tree\+Descent\+Heuristic}
\begin{DoxyCompactList}\small\item\em When descending a \doxyref{Rectangle\+Tree}{p.}{classmlpack_1_1tree_1_1RectangleTree} to insert a point, we need to have a way to choose a child node when the point isn\textquotesingle{}t enclosed by any of them. \end{DoxyCompactList}\item 
class \textbf{ R\+Tree\+Split}
\begin{DoxyCompactList}\small\item\em A Rectangle Tree has new points inserted at the bottom. \end{DoxyCompactList}\item 
class \textbf{ Space\+Split}
\item 
class \textbf{ Spill\+Tree}
\begin{DoxyCompactList}\small\item\em A hybrid spill tree is a variant of binary space trees in which the children of a node can \char`\"{}spill over\char`\"{} each other, and contain shared datapoints. \end{DoxyCompactList}\item 
class \textbf{ Traversal\+Info}
\begin{DoxyCompactList}\small\item\em The \doxyref{Traversal\+Info}{p.}{classmlpack_1_1tree_1_1TraversalInfo} class holds traversal information which is used in dual-\/tree (and single-\/tree) traversals. \end{DoxyCompactList}\item 
class \textbf{ Tree\+Traits}
\begin{DoxyCompactList}\small\item\em The \doxyref{Tree\+Traits}{p.}{classmlpack_1_1tree_1_1TreeTraits} class provides compile-\/time information on the characteristics of a given tree type. \end{DoxyCompactList}\item 
class \textbf{ Tree\+Traits$<$ Binary\+Space\+Tree$<$ Metric\+Type, Statistic\+Type, Mat\+Type, bound\+::\+Ball\+Bound, Split\+Type $>$ $>$}
\begin{DoxyCompactList}\small\item\em This is a specialization of the Tree\+Type class to the Ball\+Tree tree type. \end{DoxyCompactList}\item 
class \textbf{ Tree\+Traits$<$ Binary\+Space\+Tree$<$ Metric\+Type, Statistic\+Type, Mat\+Type, bound\+::\+Cell\+Bound, Split\+Type $>$ $>$}
\begin{DoxyCompactList}\small\item\em This is a specialization of the Tree\+Type class to the U\+B\+Tree tree type. \end{DoxyCompactList}\item 
class \textbf{ Tree\+Traits$<$ Binary\+Space\+Tree$<$ Metric\+Type, Statistic\+Type, Mat\+Type, bound\+::\+Hollow\+Ball\+Bound, Split\+Type $>$ $>$}
\begin{DoxyCompactList}\small\item\em This is a specialization of the Tree\+Type class to an arbitrary tree with Hollow\+Ball\+Bound (currently only the vantage point tree is supported). \end{DoxyCompactList}\item 
class \textbf{ Tree\+Traits$<$ Binary\+Space\+Tree$<$ Metric\+Type, Statistic\+Type, Mat\+Type, Bound\+Type, R\+P\+Tree\+Max\+Split $>$ $>$}
\begin{DoxyCompactList}\small\item\em This is a specialization of the Tree\+Type class to the max-\/split random projection tree. \end{DoxyCompactList}\item 
class \textbf{ Tree\+Traits$<$ Binary\+Space\+Tree$<$ Metric\+Type, Statistic\+Type, Mat\+Type, Bound\+Type, R\+P\+Tree\+Mean\+Split $>$ $>$}
\begin{DoxyCompactList}\small\item\em This is a specialization of the Tree\+Type class to the mean-\/split random projection tree. \end{DoxyCompactList}\item 
class \textbf{ Tree\+Traits$<$ Binary\+Space\+Tree$<$ Metric\+Type, Statistic\+Type, Mat\+Type, Bound\+Type, Split\+Type $>$ $>$}
\begin{DoxyCompactList}\small\item\em This is a specialization of the \doxyref{Tree\+Traits}{p.}{classmlpack_1_1tree_1_1TreeTraits} class to the \doxyref{Binary\+Space\+Tree}{p.}{classmlpack_1_1tree_1_1BinarySpaceTree} tree type. \end{DoxyCompactList}\item 
class \textbf{ Tree\+Traits$<$ Cover\+Tree$<$ Metric\+Type, Statistic\+Type, Mat\+Type, Root\+Point\+Policy $>$ $>$}
\begin{DoxyCompactList}\small\item\em The specialization of the \doxyref{Tree\+Traits}{p.}{classmlpack_1_1tree_1_1TreeTraits} class for the \doxyref{Cover\+Tree}{p.}{classmlpack_1_1tree_1_1CoverTree} tree type. \end{DoxyCompactList}\item 
class \textbf{ Tree\+Traits$<$ Octree$<$ Metric\+Type, Statistic\+Type, Mat\+Type $>$ $>$}
\begin{DoxyCompactList}\small\item\em This is a specialization of the \doxyref{Tree\+Traits}{p.}{classmlpack_1_1tree_1_1TreeTraits} class to the \doxyref{Octree}{p.}{classmlpack_1_1tree_1_1Octree} tree type. \end{DoxyCompactList}\item 
class \textbf{ Tree\+Traits$<$ Rectangle\+Tree$<$ Metric\+Type, Statistic\+Type, Mat\+Type, R\+Plus\+Tree\+Split$<$ Split\+Policy\+Type, Sweep\+Type $>$, Descent\+Type, Auxiliary\+Information\+Type $>$ $>$}
\begin{DoxyCompactList}\small\item\em Since the R+/\+R++ tree can not have overlapping children, we should define traits for the R+/\+R++ tree. \end{DoxyCompactList}\item 
class \textbf{ Tree\+Traits$<$ Rectangle\+Tree$<$ Metric\+Type, Statistic\+Type, Mat\+Type, Split\+Type, Descent\+Type, Auxiliary\+Information\+Type $>$ $>$}
\begin{DoxyCompactList}\small\item\em This is a specialization of the Tree\+Type class to the \doxyref{Rectangle\+Tree}{p.}{classmlpack_1_1tree_1_1RectangleTree} tree type. \end{DoxyCompactList}\item 
class \textbf{ Tree\+Traits$<$ Spill\+Tree$<$ Metric\+Type, Statistic\+Type, Mat\+Type, Hyperplane\+Type, Split\+Type $>$ $>$}
\begin{DoxyCompactList}\small\item\em This is a specialization of the Tree\+Type class to the \doxyref{Spill\+Tree}{p.}{classmlpack_1_1tree_1_1SpillTree} tree type. \end{DoxyCompactList}\item 
class \textbf{ U\+B\+Tree\+Split}
\begin{DoxyCompactList}\small\item\em Split a node into two parts according to the median address of points contained in the node. \end{DoxyCompactList}\item 
class \textbf{ Vantage\+Point\+Split}
\begin{DoxyCompactList}\small\item\em The class splits a binary space partitioning tree node according to the median distance to the vantage point. \end{DoxyCompactList}\item 
class \textbf{ X\+Tree\+Auxiliary\+Information}
\begin{DoxyCompactList}\small\item\em The \doxyref{X\+Tree\+Auxiliary\+Information}{p.}{classmlpack_1_1tree_1_1XTreeAuxiliaryInformation} class provides information specific to X trees for each node in a \doxyref{Rectangle\+Tree}{p.}{classmlpack_1_1tree_1_1RectangleTree}. \end{DoxyCompactList}\item 
class \textbf{ X\+Tree\+Split}
\begin{DoxyCompactList}\small\item\em A Rectangle Tree has new points inserted at the bottom. \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Typedefs}
\begin{DoxyCompactItemize}
\item 
{\footnotesize template$<$typename Metric\+Type $>$ }\\using \textbf{ Axis\+Orthogonal\+Hyperplane} = \textbf{ Hyperplane\+Base}$<$ \textbf{ bound\+::\+H\+Rect\+Bound}$<$ Metric\+Type $>$, \textbf{ Axis\+Parallel\+Proj\+Vector} $>$
\begin{DoxyCompactList}\small\item\em Axis\+Orthogonal\+Hyperplane represents a hyperplane orthogonal to an axis. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ Ball\+Tree} = \textbf{ Binary\+Space\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+Ball\+Bound}, \textbf{ Midpoint\+Split} $>$
\begin{DoxyCompactList}\small\item\em A midpoint-\/split ball tree. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Fitness\+Function $>$ }\\using \textbf{ Binary\+Double\+Numeric\+Split} = \textbf{ Binary\+Numeric\+Split}$<$ Fitness\+Function, double $>$
\item 
typedef boost\+::heap\+::priority\+\_\+queue$<$ \textbf{ Cosine\+Tree} $\ast$, boost\+::heap\+::compare$<$ \textbf{ Compare\+Cosine\+Node} $>$ $>$ \textbf{ Cosine\+Node\+Queue}
\item 
{\footnotesize template$<$typename Fitness\+Function  = Gini\+Gain, template$<$ typename $>$ class Numeric\+Split\+Type = Best\+Binary\+Numeric\+Split, template$<$ typename $>$ class Categorical\+Split\+Type = All\+Categorical\+Split, typename Dimension\+Select\+Type  = All\+Dimension\+Select, typename Elem\+Type  = double$>$ }\\using \textbf{ Decision\+Stump} = \textbf{ Decision\+Tree}$<$ Fitness\+Function, Numeric\+Split\+Type, Categorical\+Split\+Type, Dimension\+Select\+Type, Elem\+Type, false $>$
\begin{DoxyCompactList}\small\item\em Convenience typedef for decision stumps (single level decision trees). \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Tree\+Type $>$ }\\using \textbf{ Discrete\+Hilbert\+R\+Tree\+Auxiliary\+Information} = \textbf{ Hilbert\+R\+Tree\+Auxiliary\+Information}$<$ Tree\+Type, \textbf{ Discrete\+Hilbert\+Value} $>$
\begin{DoxyCompactList}\small\item\em The Hilbert R-\/tree, a variant of the R tree with an ordering along the Hilbert curve. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ Hilbert\+R\+Tree} = \textbf{ Rectangle\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ Hilbert\+R\+Tree\+Split}$<$ 2 $>$, \textbf{ Hilbert\+R\+Tree\+Descent\+Heuristic}, \textbf{ Discrete\+Hilbert\+R\+Tree\+Auxiliary\+Information} $>$
\item 
{\footnotesize template$<$typename Fitness\+Function $>$ }\\using \textbf{ Hoeffding\+Double\+Numeric\+Split} = \textbf{ Hoeffding\+Numeric\+Split}$<$ Fitness\+Function, double $>$
\begin{DoxyCompactList}\small\item\em Convenience typedef. \end{DoxyCompactList}\item 
typedef Streaming\+Decision\+Tree$<$ \textbf{ Hoeffding\+Tree}$<$$>$ $>$ \textbf{ Hoeffding\+Tree\+Type}
\item 
{\footnotesize template$<$typename Metric\+Type $>$ }\\using \textbf{ Hyperplane} = \textbf{ Hyperplane\+Base}$<$ \textbf{ bound\+::\+Ball\+Bound}$<$ Metric\+Type $>$, \textbf{ Proj\+Vector} $>$
\begin{DoxyCompactList}\small\item\em Hyperplane represents a general hyperplane (not necessarily axis-\/orthogonal). \end{DoxyCompactList}\item 
typedef \textbf{ Decision\+Tree}$<$ \textbf{ Information\+Gain}, \textbf{ Best\+Binary\+Numeric\+Split}, \textbf{ All\+Categorical\+Split}, \textbf{ All\+Dimension\+Select}, double, true $>$ \textbf{ I\+D3\+Decision\+Stump}
\begin{DoxyCompactList}\small\item\em Convenience typedef for I\+D3 decision stumps (single level decision trees made with the I\+D3 algorithm). \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ K\+D\+Tree} = \textbf{ Binary\+Space\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+H\+Rect\+Bound}, \textbf{ Midpoint\+Split} $>$
\begin{DoxyCompactList}\small\item\em The standard midpoint-\/split kd-\/tree. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ Max\+R\+P\+Tree} = \textbf{ Binary\+Space\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+H\+Rect\+Bound}, \textbf{ R\+P\+Tree\+Max\+Split} $>$
\begin{DoxyCompactList}\small\item\em A max-\/split random projection tree. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ Mean\+Split\+Ball\+Tree} = \textbf{ Binary\+Space\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+Ball\+Bound}, \textbf{ Mean\+Split} $>$
\begin{DoxyCompactList}\small\item\em A mean-\/split ball tree. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ Mean\+Split\+K\+D\+Tree} = \textbf{ Binary\+Space\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+H\+Rect\+Bound}, \textbf{ Mean\+Split} $>$
\begin{DoxyCompactList}\small\item\em A mean-\/split kd-\/tree. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ Mean\+S\+P\+Tree} = \textbf{ Spill\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ Axis\+Orthogonal\+Hyperplane}, \textbf{ Mean\+Space\+Split} $>$
\begin{DoxyCompactList}\small\item\em A mean-\/split hybrid spill tree. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ Non\+Ort\+Mean\+S\+P\+Tree} = \textbf{ Spill\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ Hyperplane}, \textbf{ Mean\+Space\+Split} $>$
\begin{DoxyCompactList}\small\item\em A mean-\/split hybrid spill tree considering general splitting hyperplanes (not necessarily axis-\/orthogonal). \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ Non\+Ort\+S\+P\+Tree} = \textbf{ Spill\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ Hyperplane}, \textbf{ Midpoint\+Space\+Split} $>$
\begin{DoxyCompactList}\small\item\em A hybrid spill tree considering general splitting hyperplanes (not necessarily axis-\/orthogonal). \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ R\+Plus\+Plus\+Tree} = \textbf{ Rectangle\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ R\+Plus\+Tree\+Split}$<$ \textbf{ R\+Plus\+Plus\+Tree\+Split\+Policy}, \textbf{ Minimal\+Splits\+Number\+Sweep} $>$, \textbf{ R\+Plus\+Plus\+Tree\+Descent\+Heuristic}, \textbf{ R\+Plus\+Plus\+Tree\+Auxiliary\+Information} $>$
\begin{DoxyCompactList}\small\item\em The R++ tree, a variant of the R+ tree with maximum buonding rectangles. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ R\+Plus\+Tree} = \textbf{ Rectangle\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ R\+Plus\+Tree\+Split}$<$ \textbf{ R\+Plus\+Tree\+Split\+Policy}, \textbf{ Minimal\+Coverage\+Sweep} $>$, \textbf{ R\+Plus\+Tree\+Descent\+Heuristic}, \textbf{ No\+Auxiliary\+Information} $>$
\begin{DoxyCompactList}\small\item\em The R+ tree, a variant of the R tree that avoids overlapping rectangles. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ R\+P\+Tree} = \textbf{ Binary\+Space\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+H\+Rect\+Bound}, \textbf{ R\+P\+Tree\+Mean\+Split} $>$
\begin{DoxyCompactList}\small\item\em A mean-\/split random projection tree. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ R\+Star\+Tree} = \textbf{ Rectangle\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ R\+Star\+Tree\+Split}, \textbf{ R\+Star\+Tree\+Descent\+Heuristic}, \textbf{ No\+Auxiliary\+Information} $>$
\begin{DoxyCompactList}\small\item\em The R$\ast$-\/tree, a more recent variant of the R tree. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ R\+Tree} = \textbf{ Rectangle\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ R\+Tree\+Split}, \textbf{ R\+Tree\+Descent\+Heuristic}, \textbf{ No\+Auxiliary\+Information} $>$
\begin{DoxyCompactList}\small\item\em An implementation of the R tree that satisfies the Tree\+Type policy A\+PI. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ S\+P\+Tree} = \textbf{ Spill\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ Axis\+Orthogonal\+Hyperplane}, \textbf{ Midpoint\+Space\+Split} $>$
\begin{DoxyCompactList}\small\item\em The hybrid spill tree. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ Standard\+Cover\+Tree} = \textbf{ Cover\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ First\+Point\+Is\+Root} $>$
\begin{DoxyCompactList}\small\item\em The standard cover tree, as detailed in the original cover tree paper\+: \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ U\+B\+Tree} = \textbf{ Binary\+Space\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+Cell\+Bound}, \textbf{ U\+B\+Tree\+Split} $>$
\begin{DoxyCompactList}\small\item\em The Universal B-\/tree. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ V\+P\+Tree} = \textbf{ Binary\+Space\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+Hollow\+Ball\+Bound}, \textbf{ V\+P\+Tree\+Split} $>$
\item 
{\footnotesize template$<$typename Bound\+Type , typename Mat\+Type  = arma\+::mat$>$ }\\using \textbf{ V\+P\+Tree\+Split} = \textbf{ Vantage\+Point\+Split}$<$ Bound\+Type, Mat\+Type, 100 $>$
\begin{DoxyCompactList}\small\item\em The vantage point tree (which is also called the metric tree. \end{DoxyCompactList}\item 
{\footnotesize template$<$typename Metric\+Type , typename Statistic\+Type , typename Mat\+Type $>$ }\\using \textbf{ X\+Tree} = \textbf{ Rectangle\+Tree}$<$ Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ X\+Tree\+Split}, \textbf{ R\+Tree\+Descent\+Heuristic}, \textbf{ X\+Tree\+Auxiliary\+Information} $>$
\begin{DoxyCompactList}\small\item\em The X-\/tree, a variant of the R tree with supernodes. \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Functions}
\begin{DoxyCompactItemize}
\item 
{\footnotesize template$<$bool Use\+Weights, typename Mat\+Type , typename Labels\+Type , typename Weights\+Type $>$ }\\void \textbf{ Bootstrap} (const Mat\+Type \&dataset, const Labels\+Type \&labels, const Weights\+Type \&weights, Mat\+Type \&bootstrap\+Dataset, Labels\+Type \&bootstrap\+Labels, Weights\+Type \&bootstrap\+Weights)
\begin{DoxyCompactList}\small\item\em Given a dataset, create another dataset via bootstrap sampling, with labels. \end{DoxyCompactList}\item 
{\footnotesize template$<$class Tree\+Type , class Walker $>$ }\\void \textbf{ Enumerate\+Tree} (Tree\+Type $\ast$tree, Walker \&walker)
\begin{DoxyCompactList}\small\item\em Traverses all nodes of the tree, including the inner ones. \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Variables}
\begin{DoxyCompactItemize}
\item 
const double \textbf{ M\+A\+X\+\_\+\+O\+V\+E\+R\+L\+AP} = 0.\+2
\begin{DoxyCompactList}\small\item\em The X-\/tree paper says that a maximum allowable overlap of 20\% works well. \end{DoxyCompactList}\end{DoxyCompactItemize}


\subsection{Detailed Description}
Trees and tree-\/building procedures. 



\subsection{Typedef Documentation}
\mbox{\label{namespacemlpack_1_1tree_afa85d70df69e258859143d448fbe0553}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Axis\+Orthogonal\+Hyperplane@{Axis\+Orthogonal\+Hyperplane}}
\index{Axis\+Orthogonal\+Hyperplane@{Axis\+Orthogonal\+Hyperplane}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Axis\+Orthogonal\+Hyperplane}
{\footnotesize\ttfamily using \textbf{ Axis\+Orthogonal\+Hyperplane} =  \textbf{ Hyperplane\+Base}$<$\textbf{ bound\+::\+H\+Rect\+Bound}$<$Metric\+Type$>$, \textbf{ Axis\+Parallel\+Proj\+Vector}$>$}



Axis\+Orthogonal\+Hyperplane represents a hyperplane orthogonal to an axis. 



Definition at line 145 of file hyperplane.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a9d4905444011bbd045122cc985638b32}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Ball\+Tree@{Ball\+Tree}}
\index{Ball\+Tree@{Ball\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Ball\+Tree}
{\footnotesize\ttfamily using \textbf{ Ball\+Tree} =  \textbf{ Binary\+Space\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+Ball\+Bound}, \textbf{ Midpoint\+Split}$>$}



A midpoint-\/split ball tree. 

This tree holds its points only in the leaves, similar to the K\+D\+Tree and Mean\+Split\+K\+D\+Tree. However, the bounding shape of each node is a ball, not a hyper-\/rectangle. This can make the ball tree advantageous in some higher-\/dimensional situations and for some datasets. The tree construction algorithm here is the same as Omohundro\textquotesingle{}s \textquotesingle{}K-\/d construction algorithm\textquotesingle{}, except the splitting value is the midpoint, not the median. This can result in trees that better reflect the data, although they may be unbalanced.


\begin{DoxyCode}
@techreport\{omohundro1989five,
  author=\{S.M. Omohundro\},
  title=\{Five balltree construction algorithms\},
  year=\{1989\},
  institution=\{University of California, Berkeley International Computer
      Science Institute Technical Reports\},
  number=\{TR-89-063\}
\}
\end{DoxyCode}


This template typedef satisfies the Tree\+Type policy A\+PI.

\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{Binary\+Space\+Tree}{p.}{classmlpack_1_1tree_1_1BinarySpaceTree}, \doxyref{K\+D\+Tree}{p.}{namespacemlpack_1_1tree_a73c2146f8d1da65d927c7746bfe7e750}, \doxyref{Mean\+Split\+Ball\+Tree}{p.}{namespacemlpack_1_1tree_a530d041f3f210c6097891301478e10bd} 
\end{DoxySeeAlso}


Definition at line 112 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_aa1c709206789f8ef16cf826bf965498e}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Binary\+Double\+Numeric\+Split@{Binary\+Double\+Numeric\+Split}}
\index{Binary\+Double\+Numeric\+Split@{Binary\+Double\+Numeric\+Split}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Binary\+Double\+Numeric\+Split}
{\footnotesize\ttfamily using \textbf{ Binary\+Double\+Numeric\+Split} =  \textbf{ Binary\+Numeric\+Split}$<$Fitness\+Function, double$>$}



Definition at line 128 of file binary\+\_\+numeric\+\_\+split.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a7c339b4bb20ff6160b203e3c7d78ae31}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Cosine\+Node\+Queue@{Cosine\+Node\+Queue}}
\index{Cosine\+Node\+Queue@{Cosine\+Node\+Queue}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Cosine\+Node\+Queue}
{\footnotesize\ttfamily typedef boost\+::heap\+::priority\+\_\+queue$<$\textbf{ Cosine\+Tree}$\ast$, boost\+::heap\+::compare$<$\textbf{ Compare\+Cosine\+Node}$>$ $>$ \textbf{ Cosine\+Node\+Queue}}



Definition at line 23 of file cosine\+\_\+tree.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_ae7e07a0839ee0808eac548bddbbe87a3}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Decision\+Stump@{Decision\+Stump}}
\index{Decision\+Stump@{Decision\+Stump}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Decision\+Stump}
{\footnotesize\ttfamily using \textbf{ Decision\+Stump} =  \textbf{ Decision\+Tree}$<$Fitness\+Function, Numeric\+Split\+Type, Categorical\+Split\+Type, Dimension\+Select\+Type, Elem\+Type, false$>$}



Convenience typedef for decision stumps (single level decision trees). 



Definition at line 590 of file decision\+\_\+tree.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a6168a0dfd946fa930c61e8d5b480b688}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Discrete\+Hilbert\+R\+Tree\+Auxiliary\+Information@{Discrete\+Hilbert\+R\+Tree\+Auxiliary\+Information}}
\index{Discrete\+Hilbert\+R\+Tree\+Auxiliary\+Information@{Discrete\+Hilbert\+R\+Tree\+Auxiliary\+Information}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Discrete\+Hilbert\+R\+Tree\+Auxiliary\+Information}
{\footnotesize\ttfamily using \textbf{ Discrete\+Hilbert\+R\+Tree\+Auxiliary\+Information} =  \textbf{ Hilbert\+R\+Tree\+Auxiliary\+Information}$<$Tree\+Type, \textbf{ Discrete\+Hilbert\+Value}$>$}



The Hilbert R-\/tree, a variant of the R tree with an ordering along the Hilbert curve. 

This template typedef satisfies the Tree\+Type policy A\+PI.


\begin{DoxyCode}
@inproceedings\{kamel1994r,
  author = \{Kamel, Ibrahim and Faloutsos, Christos\},
  title = \{Hilbert R-tree: An Improved R-tree Using Fractals\},
  booktitle = \{Proceedings of the 20th International Conference on Very Large Data Bases\},
  series = \{VLDB \textcolor{stringliteral}{'94\},}
\textcolor{stringliteral}{  year = \{1994\},}
\textcolor{stringliteral}{  isbn = \{1-55860-153-8\},}
\textcolor{stringliteral}{  pages = \{500--509\},}
\textcolor{stringliteral}{  numpages = \{10\},}
\textcolor{stringliteral}{  url = \{http://dl.acm.org/citation.cfm?id=645920.673001\},}
\textcolor{stringliteral}{  acmid = \{673001\},}
\textcolor{stringliteral}{  publisher = \{Morgan Kaufmann Publishers Inc.\},}
\textcolor{stringliteral}{  address = \{San Francisco, CA, USA\}}
\textcolor{stringliteral}{\}}
\end{DoxyCode}


\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{R\+Tree}{p.}{namespacemlpack_1_1tree_ae4af35641769744ba680cc934e1c1f0e}, Discrete\+Hilbert\+R\+Tree 
\end{DoxySeeAlso}


Definition at line 128 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a898fa68fa580511c0cf3c9b41ac2935f}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Hilbert\+R\+Tree@{Hilbert\+R\+Tree}}
\index{Hilbert\+R\+Tree@{Hilbert\+R\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Hilbert\+R\+Tree}
{\footnotesize\ttfamily using \textbf{ Hilbert\+R\+Tree} =  \textbf{ Rectangle\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ Hilbert\+R\+Tree\+Split}$<$2$>$, \textbf{ Hilbert\+R\+Tree\+Descent\+Heuristic}, \textbf{ Discrete\+Hilbert\+R\+Tree\+Auxiliary\+Information}$>$}



Definition at line 136 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_adab87fde9829454616f519ea70291b62}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Hoeffding\+Double\+Numeric\+Split@{Hoeffding\+Double\+Numeric\+Split}}
\index{Hoeffding\+Double\+Numeric\+Split@{Hoeffding\+Double\+Numeric\+Split}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Hoeffding\+Double\+Numeric\+Split}
{\footnotesize\ttfamily using \textbf{ Hoeffding\+Double\+Numeric\+Split} =  \textbf{ Hoeffding\+Numeric\+Split}$<$Fitness\+Function, double$>$}



Convenience typedef. 



Definition at line 148 of file hoeffding\+\_\+numeric\+\_\+split.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a3f440993550b42b081689803da5972b5}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Hoeffding\+Tree\+Type@{Hoeffding\+Tree\+Type}}
\index{Hoeffding\+Tree\+Type@{Hoeffding\+Tree\+Type}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Hoeffding\+Tree\+Type}
{\footnotesize\ttfamily typedef Streaming\+Decision\+Tree$<$\textbf{ Hoeffding\+Tree}$<$$>$ $>$ \textbf{ Hoeffding\+Tree\+Type}}



Definition at line 21 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_ac4b7e2e4fa5c9c21bba75a48365b5c19}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Hyperplane@{Hyperplane}}
\index{Hyperplane@{Hyperplane}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Hyperplane}
{\footnotesize\ttfamily using \textbf{ Hyperplane} =  \textbf{ Hyperplane\+Base}$<$\textbf{ bound\+::\+Ball\+Bound}$<$Metric\+Type$>$, \textbf{ Proj\+Vector}$>$}



Hyperplane represents a general hyperplane (not necessarily axis-\/orthogonal). 



Definition at line 151 of file hyperplane.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_ad19b696f1fb222543b22931e91dfe1ed}} 
\index{mlpack\+::tree@{mlpack\+::tree}!I\+D3\+Decision\+Stump@{I\+D3\+Decision\+Stump}}
\index{I\+D3\+Decision\+Stump@{I\+D3\+Decision\+Stump}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{I\+D3\+Decision\+Stump}
{\footnotesize\ttfamily typedef \textbf{ Decision\+Tree}$<$\textbf{ Information\+Gain}, \textbf{ Best\+Binary\+Numeric\+Split}, \textbf{ All\+Categorical\+Split}, \textbf{ All\+Dimension\+Select}, double, true$>$ \textbf{ I\+D3\+Decision\+Stump}}



Convenience typedef for I\+D3 decision stumps (single level decision trees made with the I\+D3 algorithm). 



Definition at line 601 of file decision\+\_\+tree.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a73c2146f8d1da65d927c7746bfe7e750}} 
\index{mlpack\+::tree@{mlpack\+::tree}!K\+D\+Tree@{K\+D\+Tree}}
\index{K\+D\+Tree@{K\+D\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{K\+D\+Tree}
{\footnotesize\ttfamily using \textbf{ K\+D\+Tree} =  \textbf{ Binary\+Space\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+H\+Rect\+Bound}, \textbf{ Midpoint\+Split}$>$}



The standard midpoint-\/split kd-\/tree. 

This is not the original formulation by Bentley but instead the later formulation by Deng and Moore, which only holds points in the leaves of the tree. When recursively splitting nodes, the K\+D\+Tree class select the dimension with maximum variance to split on, and picks the midpoint of the range in that dimension as the value on which to split nodes.

For more information, see the following papers.


\begin{DoxyCode}
@article\{bentley1975multidimensional,
  title=\{Multidimensional binary search trees used \textcolor{keywordflow}{for} associative searching\},
  author=\{Bentley, J.L.\},
  journal=\{Communications of the ACM\},
  volume=\{18\},
  number=\{9\},
  pages=\{509--517\},
  year=\{1975\},
  publisher=\{ACM\}
\}

@inproceedings\{deng1995multiresolution,
  title=\{Multiresolution instance-based learning\},
  author=\{Deng, K. and Moore, A.W.\},
  booktitle=\{Proceedings of the 1995 International Joint Conference on AI
      (IJCAI-95)\},
  pages=\{1233--1239\},
  year=\{1995\}
\}
\end{DoxyCode}


This template typedef satisfies the Tree\+Type policy A\+PI.

\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{Binary\+Space\+Tree}{p.}{classmlpack_1_1tree_1_1BinarySpaceTree}, \doxyref{Mean\+Split\+K\+D\+Tree}{p.}{namespacemlpack_1_1tree_a1028e6acf1fc61997237d3677cae0947} 
\end{DoxySeeAlso}


Definition at line 63 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a1b6c0a1bc747a7d103f74058863de80b}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Max\+R\+P\+Tree@{Max\+R\+P\+Tree}}
\index{Max\+R\+P\+Tree@{Max\+R\+P\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Max\+R\+P\+Tree}
{\footnotesize\ttfamily using \textbf{ Max\+R\+P\+Tree} =  \textbf{ Binary\+Space\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+H\+Rect\+Bound}, \textbf{ R\+P\+Tree\+Max\+Split}$>$}



A max-\/split random projection tree. 

When recursively splitting nodes, the Max\+Split\+R\+P\+Tree class selects a random hyperplane and splits a node by the hyperplane. The tree holds points in leaf nodes. In contrast to the k-\/d tree, children of a Max\+Split\+R\+P\+Tree node may overlap.


\begin{DoxyCode}
@inproceedings\{dasgupta2008,
  author = \{Dasgupta, Sanjoy and Freund, Yoav\},
  title = \{Random Projection Trees and Low Dimensional Manifolds\},
  booktitle = \{Proceedings of the Fortieth Annual ACM Symposium on Theory of
      Computing\},
  series = \{STOC \textcolor{stringliteral}{'08\},}
\textcolor{stringliteral}{  year = \{2008\},}
\textcolor{stringliteral}{  pages = \{537--546\},}
\textcolor{stringliteral}{  numpages = \{10\},}
\textcolor{stringliteral}{  publisher = \{ACM\},}
\textcolor{stringliteral}{  address = \{New York, NY, USA\},}
\textcolor{stringliteral}{\}}
\end{DoxyCode}


This template typedef satisfies the Tree\+Type policy A\+PI.

\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{Binary\+Space\+Tree}{p.}{classmlpack_1_1tree_1_1BinarySpaceTree}, \doxyref{Ball\+Tree}{p.}{namespacemlpack_1_1tree_a9d4905444011bbd045122cc985638b32}, \doxyref{Mean\+Split\+K\+D\+Tree}{p.}{namespacemlpack_1_1tree_a1028e6acf1fc61997237d3677cae0947} 
\end{DoxySeeAlso}


Definition at line 232 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a530d041f3f210c6097891301478e10bd}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Mean\+Split\+Ball\+Tree@{Mean\+Split\+Ball\+Tree}}
\index{Mean\+Split\+Ball\+Tree@{Mean\+Split\+Ball\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Mean\+Split\+Ball\+Tree}
{\footnotesize\ttfamily using \textbf{ Mean\+Split\+Ball\+Tree} =  \textbf{ Binary\+Space\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+Ball\+Bound}, \textbf{ Mean\+Split}$>$}



A mean-\/split ball tree. 

This tree, like the Ball\+Tree, holds its points only in the leaves. The tree construction algorithm here is the same as Omohundro\textquotesingle{}s \textquotesingle{}K-\/dc onstruction algorithm\textquotesingle{}, except the splitting value is the mean, not the median. This can result in trees that better reflect the data, although they may be unbalanced.


\begin{DoxyCode}
@techreport\{omohundro1989five,
  author=\{S.M. Omohundro\},
  title=\{Five balltree construction algorithms\},
  year=\{1989\},
  institution=\{University of California, Berkeley International Computer
      Science Institute Technical Reports\},
  number=\{TR-89-063\}
\}
\end{DoxyCode}


This template typedef satisfies the Tree\+Type policy A\+PI.

\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{Binary\+Space\+Tree}{p.}{classmlpack_1_1tree_1_1BinarySpaceTree}, \doxyref{Ball\+Tree}{p.}{namespacemlpack_1_1tree_a9d4905444011bbd045122cc985638b32}, \doxyref{Mean\+Split\+K\+D\+Tree}{p.}{namespacemlpack_1_1tree_a1028e6acf1fc61997237d3677cae0947} 
\end{DoxySeeAlso}


Definition at line 141 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a1028e6acf1fc61997237d3677cae0947}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Mean\+Split\+K\+D\+Tree@{Mean\+Split\+K\+D\+Tree}}
\index{Mean\+Split\+K\+D\+Tree@{Mean\+Split\+K\+D\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Mean\+Split\+K\+D\+Tree}
{\footnotesize\ttfamily using \textbf{ Mean\+Split\+K\+D\+Tree} =  \textbf{ Binary\+Space\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+H\+Rect\+Bound}, \textbf{ Mean\+Split}$>$}



A mean-\/split kd-\/tree. 

This is the same as the K\+D\+Tree, but this particular implementation will use the mean of the data in the split dimension as the value on which to split, instead of the midpoint. This can sometimes give better performance, but it is not always clear which type of tree is best.

This template typedef satisfies the Tree\+Type policy A\+PI.

\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{Binary\+Space\+Tree}{p.}{classmlpack_1_1tree_1_1BinarySpaceTree}, \doxyref{K\+D\+Tree}{p.}{namespacemlpack_1_1tree_a73c2146f8d1da65d927c7746bfe7e750} 
\end{DoxySeeAlso}


Definition at line 80 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a70daa44ca5882971662fb7a5410213e3}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Mean\+S\+P\+Tree@{Mean\+S\+P\+Tree}}
\index{Mean\+S\+P\+Tree@{Mean\+S\+P\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Mean\+S\+P\+Tree}
{\footnotesize\ttfamily using \textbf{ Mean\+S\+P\+Tree} =  \textbf{ Spill\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ Axis\+Orthogonal\+Hyperplane}, \textbf{ Mean\+Space\+Split}$>$}



A mean-\/split hybrid spill tree. 

This is the same as the S\+P\+Tree, but this particular implementation will use the mean of the data in the split dimension as the value on which to split, instead of the midpoint. This can sometimes give better performance, but it is not always clear which type of tree is best.

This template typedef satisfies the Tree\+Type policy A\+PI.

\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{Spill\+Tree}{p.}{classmlpack_1_1tree_1_1SpillTree}, \doxyref{S\+P\+Tree}{p.}{namespacemlpack_1_1tree_af141bd85a0c63728935fff9f5f8dd587} 
\end{DoxySeeAlso}


Definition at line 80 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a4f23fef4a51d815ae6667fb9f6920979}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Non\+Ort\+Mean\+S\+P\+Tree@{Non\+Ort\+Mean\+S\+P\+Tree}}
\index{Non\+Ort\+Mean\+S\+P\+Tree@{Non\+Ort\+Mean\+S\+P\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Non\+Ort\+Mean\+S\+P\+Tree}
{\footnotesize\ttfamily using \textbf{ Non\+Ort\+Mean\+S\+P\+Tree} =  \textbf{ Spill\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ Hyperplane}, \textbf{ Mean\+Space\+Split}$>$}



A mean-\/split hybrid spill tree considering general splitting hyperplanes (not necessarily axis-\/orthogonal). 

This is the same as the Non\+Ort\+S\+P\+Tree, but this particular implementation will use the mean of the data in the split projection as the value on which to split, instead of the midpoint. This can sometimes give better performance, but it is not always clear which type of tree is best.

This template typedef satisfies the Tree\+Type policy A\+PI.

\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{Spill\+Tree}{p.}{classmlpack_1_1tree_1_1SpillTree}, \doxyref{Mean\+S\+P\+Tree}{p.}{namespacemlpack_1_1tree_a70daa44ca5882971662fb7a5410213e3}, \doxyref{Non\+Ort\+S\+P\+Tree}{p.}{namespacemlpack_1_1tree_a6c0340182bd764bfd3e7514619cb2662} 
\end{DoxySeeAlso}


Definition at line 119 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a6c0340182bd764bfd3e7514619cb2662}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Non\+Ort\+S\+P\+Tree@{Non\+Ort\+S\+P\+Tree}}
\index{Non\+Ort\+S\+P\+Tree@{Non\+Ort\+S\+P\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Non\+Ort\+S\+P\+Tree}
{\footnotesize\ttfamily using \textbf{ Non\+Ort\+S\+P\+Tree} =  \textbf{ Spill\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ Hyperplane}, \textbf{ Midpoint\+Space\+Split}$>$}



A hybrid spill tree considering general splitting hyperplanes (not necessarily axis-\/orthogonal). 

This particular implementation will consider the midpoint of the projection of the data in the vector determined by the farthest pair of points. This can sometimes give better performance, but generally it doesn\textquotesingle{}t because it takes O(d) to calculate the projection of the query point when deciding which node to traverse, while when using a axis-\/orthogonal hyperplane, as S\+P\+Tree does, we can do it in O(1).

This template typedef satisfies the Tree\+Type policy A\+PI.

\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{Spill\+Tree}{p.}{classmlpack_1_1tree_1_1SpillTree}, \doxyref{S\+P\+Tree}{p.}{namespacemlpack_1_1tree_af141bd85a0c63728935fff9f5f8dd587} 
\end{DoxySeeAlso}


Definition at line 100 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a8d37735a4c28a68dd71ecb462c22e43c}} 
\index{mlpack\+::tree@{mlpack\+::tree}!R\+Plus\+Plus\+Tree@{R\+Plus\+Plus\+Tree}}
\index{R\+Plus\+Plus\+Tree@{R\+Plus\+Plus\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{R\+Plus\+Plus\+Tree}
{\footnotesize\ttfamily using \textbf{ R\+Plus\+Plus\+Tree} =  \textbf{ Rectangle\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ R\+Plus\+Tree\+Split}$<$\textbf{ R\+Plus\+Plus\+Tree\+Split\+Policy}, \textbf{ Minimal\+Splits\+Number\+Sweep}$>$, \textbf{ R\+Plus\+Plus\+Tree\+Descent\+Heuristic}, \textbf{ R\+Plus\+Plus\+Tree\+Auxiliary\+Information}$>$}



The R++ tree, a variant of the R+ tree with maximum buonding rectangles. 

This template typedef satisfies the Tree\+Type policy A\+PI.


\begin{DoxyCode}
@inproceedings\{sumak2014r,
  author = \{\{\(\backslash\)v\{S\}\}um\{\(\backslash\)\textcolor{stringliteral}{'a\}k, Martin and Gursk\{\(\backslash\)'y\}, Peter\},}
\textcolor{stringliteral}{  title = \{R++-Tree: An Efficient Spatial Access Method for Highly Redundant}
\textcolor{stringliteral}{     Point Data\},}
\textcolor{stringliteral}{  booktitle = \{New Trends in Databases and Information Systems: 17th East}
\textcolor{stringliteral}{     European Conference on Advances in Databases and Information Systems\},}
\textcolor{stringliteral}{  year = \{2014\},}
\textcolor{stringliteral}{  isbn = \{978-3-319-01863-8\},}
\textcolor{stringliteral}{  pages = \{37--44\},}
\textcolor{stringliteral}{  publisher = \{Springer International Publishing\},}
\textcolor{stringliteral}{\}}
\end{DoxyCode}


\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{R\+Tree}{p.}{namespacemlpack_1_1tree_ae4af35641769744ba680cc934e1c1f0e}, \doxyref{R\+Tree}{p.}{namespacemlpack_1_1tree_ae4af35641769744ba680cc934e1c1f0e}, \doxyref{R\+Plus\+Tree}{p.}{namespacemlpack_1_1tree_ab824e5f1c342bc76e5b2def29d2cb2e5}, \doxyref{R\+Plus\+Plus\+Tree}{p.}{namespacemlpack_1_1tree_a8d37735a4c28a68dd71ecb462c22e43c} 
\end{DoxySeeAlso}


Definition at line 197 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_ab824e5f1c342bc76e5b2def29d2cb2e5}} 
\index{mlpack\+::tree@{mlpack\+::tree}!R\+Plus\+Tree@{R\+Plus\+Tree}}
\index{R\+Plus\+Tree@{R\+Plus\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{R\+Plus\+Tree}
{\footnotesize\ttfamily using \textbf{ R\+Plus\+Tree} =  \textbf{ Rectangle\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ R\+Plus\+Tree\+Split}$<$\textbf{ R\+Plus\+Tree\+Split\+Policy}, \textbf{ Minimal\+Coverage\+Sweep}$>$, \textbf{ R\+Plus\+Tree\+Descent\+Heuristic}, \textbf{ No\+Auxiliary\+Information}$>$}



The R+ tree, a variant of the R tree that avoids overlapping rectangles. 

The implementation is modified from the original paper implementation. This template typedef satisfies the Tree\+Type policy A\+PI.


\begin{DoxyCode}
@inproceedings\{sellis1987r,
  author = \{Sellis, Timos K. and Roussopoulos, Nick and Faloutsos, Christos\},
  title = \{The R+-Tree: A Dynamic Index \textcolor{keywordflow}{for} Multi-Dimensional Objects\},
  booktitle = \{Proceedings of the 13th International Conference on Very
     Large Data Bases\},
  series = \{VLDB \textcolor{stringliteral}{'87\},}
\textcolor{stringliteral}{  year = \{1987\},}
\textcolor{stringliteral}{  isbn = \{0-934613-46-X\},}
\textcolor{stringliteral}{  pages = \{507--518\},}
\textcolor{stringliteral}{  numpages = \{12\},}
\textcolor{stringliteral}{  publisher = \{Morgan Kaufmann Publishers Inc.\},}
\textcolor{stringliteral}{  address = \{San Francisco, CA, USA\},}
\textcolor{stringliteral}{\}}
\end{DoxyCode}


\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{R\+Tree}{p.}{namespacemlpack_1_1tree_ae4af35641769744ba680cc934e1c1f0e}, \doxyref{R\+Tree}{p.}{namespacemlpack_1_1tree_ae4af35641769744ba680cc934e1c1f0e}, \doxyref{R\+Plus\+Tree}{p.}{namespacemlpack_1_1tree_ab824e5f1c342bc76e5b2def29d2cb2e5} 
\end{DoxySeeAlso}


Definition at line 168 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a13e8453de3098f2c2d4770a2266cc009}} 
\index{mlpack\+::tree@{mlpack\+::tree}!R\+P\+Tree@{R\+P\+Tree}}
\index{R\+P\+Tree@{R\+P\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{R\+P\+Tree}
{\footnotesize\ttfamily using \textbf{ R\+P\+Tree} =  \textbf{ Binary\+Space\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+H\+Rect\+Bound}, \textbf{ R\+P\+Tree\+Mean\+Split}$>$}



A mean-\/split random projection tree. 

When recursively splitting nodes, the R\+P\+Tree class may perform one of two different kinds of split. Depending on the diameter and the average distance between points, the node may be split by a random hyperplane or according to the distance from the mean point. The tree holds points in leaf nodes. In contrast to the k-\/d tree, children of a Max\+Split\+R\+P\+Tree node may overlap.


\begin{DoxyCode}
@inproceedings\{dasgupta2008,
  author = \{Dasgupta, Sanjoy and Freund, Yoav\},
  title = \{Random Projection Trees and Low Dimensional Manifolds\},
  booktitle = \{Proceedings of the Fortieth Annual ACM Symposium on Theory of
      Computing\},
  series = \{STOC \textcolor{stringliteral}{'08\},}
\textcolor{stringliteral}{  year = \{2008\},}
\textcolor{stringliteral}{  pages = \{537--546\},}
\textcolor{stringliteral}{  numpages = \{10\},}
\textcolor{stringliteral}{  publisher = \{ACM\},}
\textcolor{stringliteral}{  address = \{New York, NY, USA\},}
\textcolor{stringliteral}{\}}
\end{DoxyCode}


This template typedef satisfies the Tree\+Type policy A\+PI.

\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{Binary\+Space\+Tree}{p.}{classmlpack_1_1tree_1_1BinarySpaceTree}, \doxyref{Ball\+Tree}{p.}{namespacemlpack_1_1tree_a9d4905444011bbd045122cc985638b32}, \doxyref{Mean\+Split\+K\+D\+Tree}{p.}{namespacemlpack_1_1tree_a1028e6acf1fc61997237d3677cae0947} 
\end{DoxySeeAlso}


Definition at line 266 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a879db9c5c88d62f13f4a1667bc5adf5c}} 
\index{mlpack\+::tree@{mlpack\+::tree}!R\+Star\+Tree@{R\+Star\+Tree}}
\index{R\+Star\+Tree@{R\+Star\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{R\+Star\+Tree}
{\footnotesize\ttfamily using \textbf{ R\+Star\+Tree} =  \textbf{ Rectangle\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ R\+Star\+Tree\+Split}, \textbf{ R\+Star\+Tree\+Descent\+Heuristic}, \textbf{ No\+Auxiliary\+Information}$>$}



The R$\ast$-\/tree, a more recent variant of the R tree. 

This template typedef satisfies the Tree\+Type policy A\+PI.


\begin{DoxyCode}
@inproceedings\{beckmann1990r,
  title=\{The R*-tree: an efficient and robust access method \textcolor{keywordflow}{for} points and
      rectangles\},
  author=\{Beckmann, N. and Kriegel, H.-P. and Schneider, R. and Seeger, B.\},
  booktitle=\{Proceedings of the 1990 ACM SIGMOD International Conference on
      Management of Data (SIGMOD \textcolor{stringliteral}{'90)\},}
\textcolor{stringliteral}{  volume=\{19\},}
\textcolor{stringliteral}{  number=\{2\},}
\textcolor{stringliteral}{  year=\{1990\},}
\textcolor{stringliteral}{  publisher=\{ACM\}}
\textcolor{stringliteral}{\}}
\end{DoxyCode}


\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{R\+Tree}{p.}{namespacemlpack_1_1tree_ae4af35641769744ba680cc934e1c1f0e} 
\end{DoxySeeAlso}


Definition at line 75 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_ae4af35641769744ba680cc934e1c1f0e}} 
\index{mlpack\+::tree@{mlpack\+::tree}!R\+Tree@{R\+Tree}}
\index{R\+Tree@{R\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{R\+Tree}
{\footnotesize\ttfamily using \textbf{ R\+Tree} =  \textbf{ Rectangle\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ R\+Tree\+Split}, \textbf{ R\+Tree\+Descent\+Heuristic}, \textbf{ No\+Auxiliary\+Information}$>$}



An implementation of the R tree that satisfies the Tree\+Type policy A\+PI. 

This is the same R-\/tree structure as proposed by Guttman\+:


\begin{DoxyCode}
@inproceedings\{guttman1984r,
  title=\{R-trees: a dynamic index structure \textcolor{keywordflow}{for} spatial searching\},
  author=\{Guttman, A.\},
  booktitle=\{Proceedings of the 1984 ACM SIGMOD International Conference on
      Management of Data (SIGMOD \textcolor{stringliteral}{'84)\},}
\textcolor{stringliteral}{  volume=\{14\},}
\textcolor{stringliteral}{  number=\{2\},}
\textcolor{stringliteral}{  year=\{1984\},}
\textcolor{stringliteral}{  publisher=\{ACM\}}
\textcolor{stringliteral}{\}}
\end{DoxyCode}


\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{R\+Star\+Tree}{p.}{namespacemlpack_1_1tree_a879db9c5c88d62f13f4a1667bc5adf5c} 
\end{DoxySeeAlso}


Definition at line 47 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_af141bd85a0c63728935fff9f5f8dd587}} 
\index{mlpack\+::tree@{mlpack\+::tree}!S\+P\+Tree@{S\+P\+Tree}}
\index{S\+P\+Tree@{S\+P\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{S\+P\+Tree}
{\footnotesize\ttfamily using \textbf{ S\+P\+Tree} =  \textbf{ Spill\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ Axis\+Orthogonal\+Hyperplane}, \textbf{ Midpoint\+Space\+Split}$>$}



The hybrid spill tree. 

It is a variant of metric-\/trees in which the children of a node can \char`\"{}spill over\char`\"{} onto each other, and contain shared datapoints.

When recursively splitting nodes, the S\+P\+Tree class select the dimension with maximum width to split on, and picks the midpoint of the range in that dimension as the value on which to split nodes.

In each case a \char`\"{}overlapping buffer\char`\"{} is defined, included points at a distance less than tau from the decision boundary defined by the midpoint.

For each node, we first split the points considering the overlapping buffer. If either of its children contains more than rho fraction of the total points we undo the overlapping splitting. Instead a conventional partition is used. In this way, we can ensure that each split reduces the number of points of a node by at least a constant factor.

For more information, see the following paper.


\begin{DoxyCode}
@inproceedings\{
  author = \{Ting Liu, Andrew W. Moore, Alexander Gray and Ke Yang\},
  title = \{An Investigation of Practical Approximate Nearest Neighbor
    Algorithms\},
  booktitle = \{Advances in Neural Information Processing Systems 17\},
  year = \{2005\},
  pages = \{825--832\}
\}
\end{DoxyCode}


This template typedef satisfies the Tree\+Type policy A\+PI.

\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{Spill\+Tree}{p.}{classmlpack_1_1tree_1_1SpillTree}, \doxyref{Mean\+S\+P\+Tree}{p.}{namespacemlpack_1_1tree_a70daa44ca5882971662fb7a5410213e3} 
\end{DoxySeeAlso}


Definition at line 62 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a6ed9d585969e7837af0d41e0c3975602}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Standard\+Cover\+Tree@{Standard\+Cover\+Tree}}
\index{Standard\+Cover\+Tree@{Standard\+Cover\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Standard\+Cover\+Tree}
{\footnotesize\ttfamily using \textbf{ Standard\+Cover\+Tree} =  \textbf{ Cover\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ First\+Point\+Is\+Root}$>$}



The standard cover tree, as detailed in the original cover tree paper\+: 


\begin{DoxyCode}
@inproceedings\{
  author=\{Beygelzimer, A. and Kakade, S. and Langford, J.\},
  title=\{Cover trees \textcolor{keywordflow}{for} nearest neighbor\},
  booktitle=\{Proceedings of the 23rd International Conference on Machine
      Learning (ICML 2006)\},
  pages=\{97--104\},
  year=\{2006\}
\}
\end{DoxyCode}


This template typedef satisfies the requirements of the Tree\+Type A\+PI.

\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{Cover\+Tree}{p.}{classmlpack_1_1tree_1_1CoverTree} 
\end{DoxySeeAlso}


Definition at line 42 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_afef9300f198bfdcb0272cc71fcd1ef12}} 
\index{mlpack\+::tree@{mlpack\+::tree}!U\+B\+Tree@{U\+B\+Tree}}
\index{U\+B\+Tree@{U\+B\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{U\+B\+Tree}
{\footnotesize\ttfamily using \textbf{ U\+B\+Tree} =  \textbf{ Binary\+Space\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+Cell\+Bound}, \textbf{ U\+B\+Tree\+Split}$>$}



The Universal B-\/tree. 

When recursively splitting nodes, the class calculates addresses of all points and splits each node according to the median address. Children may overlap since the implementation of a tighter bound requires a lot of arithmetic operations. In order to get a tighter bound increase the Cell\+Bound\+::max\+Num\+Bounds constant.


\begin{DoxyCode}
@inproceedings\{bayer1997,
  author = \{Bayer, Rudolf\},
  title = \{The Universal B-Tree \textcolor{keywordflow}{for} Multidimensional Indexing: General
      Concepts\},
  booktitle = \{Proceedings of the International Conference on Worldwide
      Computing and Its Applications\},
  series = \{WWCA \textcolor{stringliteral}{'97\},}
\textcolor{stringliteral}{  year = \{1997\},}
\textcolor{stringliteral}{  isbn = \{3-540-63343-X\},}
\textcolor{stringliteral}{  pages = \{198--209\},}
\textcolor{stringliteral}{  numpages = \{12\},}
\textcolor{stringliteral}{  publisher = \{Springer-Verlag\},}
\textcolor{stringliteral}{  address = \{London, UK, UK\},}
\textcolor{stringliteral}{\}}
\end{DoxyCode}


This template typedef satisfies the Tree\+Type policy A\+PI.

\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{Binary\+Space\+Tree}{p.}{classmlpack_1_1tree_1_1BinarySpaceTree}, \doxyref{Ball\+Tree}{p.}{namespacemlpack_1_1tree_a9d4905444011bbd045122cc985638b32}, \doxyref{Mean\+Split\+K\+D\+Tree}{p.}{namespacemlpack_1_1tree_a1028e6acf1fc61997237d3677cae0947} 
\end{DoxySeeAlso}


Definition at line 301 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a2cc107a67c3011cc95797065a0867d7e}} 
\index{mlpack\+::tree@{mlpack\+::tree}!V\+P\+Tree@{V\+P\+Tree}}
\index{V\+P\+Tree@{V\+P\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{V\+P\+Tree}
{\footnotesize\ttfamily using \textbf{ V\+P\+Tree} =  \textbf{ Binary\+Space\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ bound\+::\+Hollow\+Ball\+Bound}, \textbf{ V\+P\+Tree\+Split}$>$}



Definition at line 199 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_aa93c424ec92d738156c120337109b79e}} 
\index{mlpack\+::tree@{mlpack\+::tree}!V\+P\+Tree\+Split@{V\+P\+Tree\+Split}}
\index{V\+P\+Tree\+Split@{V\+P\+Tree\+Split}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{V\+P\+Tree\+Split}
{\footnotesize\ttfamily using \textbf{ V\+P\+Tree\+Split} =  \textbf{ Vantage\+Point\+Split}$<$Bound\+Type, Mat\+Type, 100$>$}



The vantage point tree (which is also called the metric tree. 

Vantage point trees and metric trees were invented independently by Yianilos an Uhlmann) is a kind of the binary space tree. When recursively splitting nodes, the V\+P\+Tree class selects the vantage point and splits the node according to the distance to this point. Thus, points that are closer to the vantage point form the inner subtree. Other points form the outer subtree. The vantage point is contained in the first (inner) node.

This implementation differs from the original algorithms. Namely, vantage points are not contained in intermediate nodes. The tree has points only in the leaves of the tree.

For more information, see the following papers.


\begin{DoxyCode}
@inproceedings\{yianilos1993vptrees,
  author = \{Yianilos, Peter N.\},
  title = \{Data Structures and Algorithms \textcolor{keywordflow}{for} Nearest Neighbor Search in
      General Metric Spaces\},
  booktitle = \{Proceedings of the Fourth Annual ACM-SIAM Symposium on
      Discrete Algorithms\},
  series = \{SODA \textcolor{stringliteral}{'93\},}
\textcolor{stringliteral}{  year = \{1993\},}
\textcolor{stringliteral}{  isbn = \{0-89871-313-7\},}
\textcolor{stringliteral}{  pages = \{311--321\},}
\textcolor{stringliteral}{  numpages = \{11\},}
\textcolor{stringliteral}{  publisher = \{Society for Industrial and Applied Mathematics\},}
\textcolor{stringliteral}{  address = \{Philadelphia, PA, USA\}}
\textcolor{stringliteral}{\}}
\textcolor{stringliteral}{}
\textcolor{stringliteral}{@article\{uhlmann1991metrictrees,}
\textcolor{stringliteral}{  author = \{Jeffrey K. Uhlmann\},}
\textcolor{stringliteral}{  title = \{Satisfying general proximity / similarity queries with metric}
\textcolor{stringliteral}{      trees\},}
\textcolor{stringliteral}{  journal = \{Information Processing Letters\},}
\textcolor{stringliteral}{  volume = \{40\},}
\textcolor{stringliteral}{  number = \{4\},}
\textcolor{stringliteral}{  pages = \{175 - 179\},}
\textcolor{stringliteral}{  year = \{1991\},}
\textcolor{stringliteral}{\}}
\end{DoxyCode}


This template typedef satisfies the Tree\+Type policy A\+PI.

\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{Binary\+Space\+Tree}{p.}{classmlpack_1_1tree_1_1BinarySpaceTree}, Vantage\+Point\+Tree, \doxyref{V\+P\+Tree}{p.}{namespacemlpack_1_1tree_a2cc107a67c3011cc95797065a0867d7e} 
\end{DoxySeeAlso}


Definition at line 192 of file typedef.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_a78cd0a7cf4615cae990696f90aea84c4}} 
\index{mlpack\+::tree@{mlpack\+::tree}!X\+Tree@{X\+Tree}}
\index{X\+Tree@{X\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{X\+Tree}
{\footnotesize\ttfamily using \textbf{ X\+Tree} =  \textbf{ Rectangle\+Tree}$<$Metric\+Type, Statistic\+Type, Mat\+Type, \textbf{ X\+Tree\+Split}, \textbf{ R\+Tree\+Descent\+Heuristic}, \textbf{ X\+Tree\+Auxiliary\+Information}$>$}



The X-\/tree, a variant of the R tree with supernodes. 

This template typedef satisfies the Tree\+Type policy A\+PI.


\begin{DoxyCode}
@inproceedings\{berchtold1996r,
  title = \{The X-Tree: An Index Structure \textcolor{keywordflow}{for} High--Dimensional Data\},
  author = \{Berchtold, Stefan and Keim, Daniel A. and Kriegel, Hans-Peter\},
  booktitle = \{Proc. 22th Int. Conf. on Very Large Databases (VLDB\textcolor{stringliteral}{'96), Bombay, India\},}
\textcolor{stringliteral}{  editor = \{Vijayaraman, T. and Buchmann, Alex and Mohan, C. and Sarda, N.\},}
\textcolor{stringliteral}{  pages = \{28--39\},}
\textcolor{stringliteral}{  year = \{1996\},}
\textcolor{stringliteral}{  publisher = \{Morgan Kaufmann\}}
\textcolor{stringliteral}{\}}
\end{DoxyCode}


\begin{DoxySeeAlso}{See also}
\doxyref{The Tree\+Type policy in mlpack}{p.}{trees}, \doxyref{R\+Tree}{p.}{namespacemlpack_1_1tree_ae4af35641769744ba680cc934e1c1f0e}, \doxyref{R\+Star\+Tree}{p.}{namespacemlpack_1_1tree_a879db9c5c88d62f13f4a1667bc5adf5c} 
\end{DoxySeeAlso}


Definition at line 101 of file typedef.\+hpp.



\subsection{Function Documentation}
\mbox{\label{namespacemlpack_1_1tree_aebb06bf0ada277e56a77d80cd1985dbe}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Bootstrap@{Bootstrap}}
\index{Bootstrap@{Bootstrap}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Bootstrap()}
{\footnotesize\ttfamily void mlpack\+::tree\+::\+Bootstrap (\begin{DoxyParamCaption}\item[{const Mat\+Type \&}]{dataset,  }\item[{const Labels\+Type \&}]{labels,  }\item[{const Weights\+Type \&}]{weights,  }\item[{Mat\+Type \&}]{bootstrap\+Dataset,  }\item[{Labels\+Type \&}]{bootstrap\+Labels,  }\item[{Weights\+Type \&}]{bootstrap\+Weights }\end{DoxyParamCaption})}



Given a dataset, create another dataset via bootstrap sampling, with labels. 



Definition at line 26 of file bootstrap.\+hpp.

\mbox{\label{namespacemlpack_1_1tree_abab37b0038f14ab4dcdf83c60468e923}} 
\index{mlpack\+::tree@{mlpack\+::tree}!Enumerate\+Tree@{Enumerate\+Tree}}
\index{Enumerate\+Tree@{Enumerate\+Tree}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{Enumerate\+Tree()}
{\footnotesize\ttfamily void mlpack\+::tree\+::\+Enumerate\+Tree (\begin{DoxyParamCaption}\item[{Tree\+Type $\ast$}]{tree,  }\item[{Walker \&}]{walker }\end{DoxyParamCaption})\hspace{0.3cm}{\ttfamily [inline]}}



Traverses all nodes of the tree, including the inner ones. 

On each node two methods of the {\ttfamily enumer} are called\+:

Enter(\+Tree\+Type$\ast$ node, Tree\+Type$\ast$ parent); Leave(\+Tree\+Type$\ast$ node, Tree\+Type$\ast$ parent);


\begin{DoxyParams}{Parameters}
{\em walker} & An instance of custom class, receiver of the enumeration. \\
\hline
\end{DoxyParams}


Definition at line 55 of file enumerate\+\_\+tree.\+hpp.



References mlpack\+::tree\+::enumerate\+::\+Enumerate\+Tree\+Impl().



\subsection{Variable Documentation}
\mbox{\label{namespacemlpack_1_1tree_a23057f6f52ed3b029f53aacbc1fcec85}} 
\index{mlpack\+::tree@{mlpack\+::tree}!M\+A\+X\+\_\+\+O\+V\+E\+R\+L\+AP@{M\+A\+X\+\_\+\+O\+V\+E\+R\+L\+AP}}
\index{M\+A\+X\+\_\+\+O\+V\+E\+R\+L\+AP@{M\+A\+X\+\_\+\+O\+V\+E\+R\+L\+AP}!mlpack\+::tree@{mlpack\+::tree}}
\subsubsection{M\+A\+X\+\_\+\+O\+V\+E\+R\+L\+AP}
{\footnotesize\ttfamily const double M\+A\+X\+\_\+\+O\+V\+E\+R\+L\+AP = 0.\+2}



The X-\/tree paper says that a maximum allowable overlap of 20\% works well. 

This code should eventually be refactored so as to avoid polluting \doxyref{mlpack\+::tree}{p.}{namespacemlpack_1_1tree} with this random double. 

Definition at line 29 of file x\+\_\+tree\+\_\+split.\+hpp.