shark::BinaryTree< InputT > Class Template Referenceabstract

Super class of binary space-partitioning trees. More...

#include <shark/Models/Trees/BinaryTree.h>

+ Inheritance diagram for shark::BinaryTree< InputT >:

Public Member Functions

 BinaryTree (std::size_t size)
 Root node constructor: build the tree from data. More...
 
virtual ~BinaryTree ()
 Destroy the tree and its internal data structures. More...
 
BinaryTreeparent ()
 parent node More...
 
const BinaryTreeparent () const
 parent node More...
 
bool hasChildren () const
 
bool isLeaf () const
 
BinaryTreeleft ()
 "left" sub-node of the binary tree More...
 
const BinaryTreeleft () const
 "left" sub-node of the binary tree More...
 
BinaryTreeright ()
 "right" sub-node of the binary tree More...
 
const BinaryTreeright () const
 "right" sub-node of the binary tree More...
 
std::size_t size () const
 number of points inside the space represented by this node More...
 
std::size_t nodes () const
 number of sub-nodes in this tree (including the node itself) More...
 
std::size_t index (std::size_t point) const
 
double distanceFromPlane (value_type const &point) const
 Function describing the separation of space. More...
 
double threshold () const
 Separation threshold. More...
 
bool isLeft (value_type const &point) const
 
bool isRight (value_type const &point) const
 
virtual AbstractKernelFunction< value_type > const * kernel () const
 If the tree uses a kernel metric, returns a pointer to the kernel object, else NULL. More...
 
virtual double squaredDistanceLowerBound (value_type const &point) const =0
 Compute lower bound on the squared distance to the space cell. More...
 

Protected Member Functions

 BinaryTree (BinaryTree *parent, std::size_t *list, std::size_t size)
 Sub-node constructor. More...
 
virtual double funct (value_type const &point) const =0
 Function describing the separation of space. More...
 
template<class Range1 , class Range2 >
Range2::iterator splitList (Range1 &values, Range2 &points)
 Split the data in the point list and calculate the treshold accordingly. More...
 

Protected Attributes

BinaryTreemep_parent
 parent node More...
 
BinaryTreemp_left
 "left" child node More...
 
BinaryTreemp_right
 "right" child node More...
 
std::size_t * mp_indexList
 list of indices to points in the dataset More...
 
std::size_t m_size
 number of points in this node More...
 
std::size_t m_nodes
 number of nodes in the sub-tree represented by this node More...
 
double m_threshold
 threshold for the separating function More...
 

Detailed Description

template<class InputT>
class shark::BinaryTree< InputT >

Super class of binary space-partitioning trees.

This class represents a generic node in a binary space-partitioning tree. At each junction the space cell represented by the parent node is split into sub-cells by thresholding a real-valued function. Different sub-classes implement different such functions. The absolute value of the function minus the threshold m_threshold must represent the distance to the separating hyper-surface in the underlying metric. This allows for linear separation, but also for kernel-induced feature spaces and other embeddings.

Definition at line 128 of file BinaryTree.h.

Constructor & Destructor Documentation

◆ BinaryTree() [1/2]

template<class InputT>
shark::BinaryTree< InputT >::BinaryTree ( std::size_t  size)
inline

Root node constructor: build the tree from data.

Please refer the specific sub-classes such as KDTree for examples of how the binary tree is built.

Definition at line 138 of file BinaryTree.h.

◆ ~BinaryTree()

template<class InputT>
virtual shark::BinaryTree< InputT >::~BinaryTree ( )
inlinevirtual

Destroy the tree and its internal data structures.

Definition at line 155 of file BinaryTree.h.

◆ BinaryTree() [2/2]

template<class InputT>
shark::BinaryTree< InputT >::BinaryTree ( BinaryTree< InputT > *  parent,
std::size_t *  list,
std::size_t  size 
)
inlineprotected

Sub-node constructor.

Initialize a sub-node

Definition at line 266 of file BinaryTree.h.

Member Function Documentation

◆ distanceFromPlane()

template<class InputT>
double shark::BinaryTree< InputT >::distanceFromPlane ( value_type const &  point) const
inline

Function describing the separation of space.

This function is shifted by subtracting the threshold from the virtual function "funct" (which acts as a "decision" function to split space into sub-cells). The result of this function describes "signed" distance to the separation boundary, and the two cells are thresholded at zero. We obtain the two cells:
left ("negative") cell: {x | distance(x) < 0}
right ("positive") cell {x | distance(x) >= 0}

Definition at line 224 of file BinaryTree.h.

Referenced by shark::LCTree< VectorType, CuttingAccuracy >::squaredDistanceLowerBound().

◆ funct()

template<class InputT>
virtual double shark::BinaryTree< InputT >::funct ( value_type const &  point) const
protectedpure virtual

Function describing the separation of space.

This is the primary interface for customizing sub-classes.
This function splits the space represented by the node by thresholding at m_threshold. The "negative" cell, represented in the "left" sub-node, represents the space {x | funct(x) < threshold}. The "positive" cell, represented by the "right" sub-node, represents {x | funct(x) >= threshold}. The function needs to be normalized such that |f(x) - f(y)| is the distance between {z | f(z) = f(x)} and {z | f(z) = f(y)}, w.r.t. the distance function also used by the virtual function squaredDistanceLowerBound. The exact distance function does not matter as long as the same distance function is used in both cases.

Implemented in shark::KDTree< InputT >.

◆ hasChildren()

template<class InputT>
bool shark::BinaryTree< InputT >::hasChildren ( ) const
inline

◆ index()

template<class InputT>
std::size_t shark::BinaryTree< InputT >::index ( std::size_t  point) const
inline

Definition at line 204 of file BinaryTree.h.

Referenced by shark::KDTree< InputT >::squaredDistanceLowerBound().

◆ isLeaf()

template<class InputT>
bool shark::BinaryTree< InputT >::isLeaf ( ) const
inline

Is this a leaf node? Opposite of hasChildren()

Definition at line 179 of file BinaryTree.h.

Referenced by shark::KDTree< InputT >::squaredDistanceLowerBound().

◆ isLeft()

template<class InputT>
bool shark::BinaryTree< InputT >::isLeft ( value_type const &  point) const
inline

return true if the reference point belongs to the "left" sub-node, or to the "negative" sub-cell.

Definition at line 235 of file BinaryTree.h.

Referenced by shark::HierarchicalClustering< InputT >::hardMembership(), and shark::IterativeNNQuery< DataContainer >::IterativeNNQuery().

◆ isRight()

template<class InputT>
bool shark::BinaryTree< InputT >::isRight ( value_type const &  point) const
inline

return true if the reference point belongs to the "right" sub-node, or to the "positive" sub-cell.

Definition at line 240 of file BinaryTree.h.

◆ kernel()

template<class InputT>
virtual AbstractKernelFunction<value_type> const* shark::BinaryTree< InputT >::kernel ( ) const
inlinevirtual

If the tree uses a kernel metric, returns a pointer to the kernel object, else NULL.

Definition at line 244 of file BinaryTree.h.

◆ left() [1/2]

template<class InputT>
BinaryTree* shark::BinaryTree< InputT >::left ( )
inline

"left" sub-node of the binary tree

Definition at line 183 of file BinaryTree.h.

Referenced by shark::IterativeNNQuery< DataContainer >::IterativeNNQuery(), and shark::IterativeNNQuery< DataContainer >::queuesize().

◆ left() [2/2]

template<class InputT>
const BinaryTree* shark::BinaryTree< InputT >::left ( ) const
inline

"left" sub-node of the binary tree

Definition at line 186 of file BinaryTree.h.

◆ nodes()

template<class InputT>
std::size_t shark::BinaryTree< InputT >::nodes ( ) const
inline

number of sub-nodes in this tree (including the node itself)

Definition at line 201 of file BinaryTree.h.

Referenced by shark::HierarchicalClustering< InputT >::numberOfClusters().

◆ parent() [1/2]

template<class InputT>
BinaryTree* shark::BinaryTree< InputT >::parent ( )
inline

parent node

Definition at line 166 of file BinaryTree.h.

Referenced by shark::KDTree< InputT >::lower(), and shark::KDTree< InputT >::upper().

◆ parent() [2/2]

template<class InputT>
const BinaryTree* shark::BinaryTree< InputT >::parent ( ) const
inline

parent node

Definition at line 169 of file BinaryTree.h.

◆ right() [1/2]

template<class InputT>
BinaryTree* shark::BinaryTree< InputT >::right ( )
inline

"right" sub-node of the binary tree

Definition at line 190 of file BinaryTree.h.

Referenced by shark::IterativeNNQuery< DataContainer >::IterativeNNQuery(), and shark::IterativeNNQuery< DataContainer >::queuesize().

◆ right() [2/2]

template<class InputT>
const BinaryTree* shark::BinaryTree< InputT >::right ( ) const
inline

"right" sub-node of the binary tree

Definition at line 193 of file BinaryTree.h.

◆ size()

template<class InputT>
std::size_t shark::BinaryTree< InputT >::size ( ) const
inline

number of points inside the space represented by this node

Definition at line 197 of file BinaryTree.h.

Referenced by shark::KDTree< InputT >::squaredDistanceLowerBound().

◆ splitList()

template<class InputT>
template<class Range1 , class Range2 >
Range2::iterator shark::BinaryTree< InputT >::splitList ( Range1 &  values,
Range2 &  points 
)
inlineprotected

Split the data in the point list and calculate the treshold accordingly.

The method computes the optimal threshold given the distance of every element of the set and partitions the point range accordingly

Parameters
valuesthe value of every point returned by funct(point)
pointsthe points themselves
Returns
returns the position were the point list was split

Definition at line 306 of file BinaryTree.h.

◆ squaredDistanceLowerBound()

template<class InputT>
virtual double shark::BinaryTree< InputT >::squaredDistanceLowerBound ( value_type const &  point) const
pure virtual

Compute lower bound on the squared distance to the space cell.

For efficient use of the triangle inequality the space cell represented by each node needs to provide (a lower bound on) the distance of a query point to the space cell represented by this node. Search is fast if this bound is tight.

Implemented in shark::KDTree< InputT >.

Referenced by shark::IterativeNNQuery< DataContainer >::queuesize().

◆ threshold()

template<class InputT>
double shark::BinaryTree< InputT >::threshold ( ) const
inline

Member Data Documentation

◆ m_nodes

template<class InputT>
std::size_t shark::BinaryTree< InputT >::m_nodes
protected

◆ m_size

◆ m_threshold

template<class InputT>
double shark::BinaryTree< InputT >::m_threshold
protected

threshold for the separating function

Definition at line 355 of file BinaryTree.h.

◆ mep_parent

◆ mp_indexList

template<class InputT>
std::size_t* shark::BinaryTree< InputT >::mp_indexList
protected

◆ mp_left

◆ mp_right


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