LC-tree, a binary space-partitioning tree. More...

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

Inheritance diagram for shark::LCTree< VectorType, CuttingAccuracy >:

Public Member Functions
	LCTree (Data< RealVector > const &dataset, TreeConstruction tc=TreeConstruction())

double	squaredDistanceLowerBound (VectorType const &reference) const

Public Member Functions inherited from shark::BinaryTree< InputT >
	BinaryTree (std::size_t size)
	Root node constructor: build the tree from data.

virtual	~BinaryTree ()
	Destroy the tree and its internal data structures.

BinaryTree *	parent ()
	parent node

const BinaryTree *	parent () const
	parent node

bool	hasChildren () const

bool	isLeaf () const

BinaryTree *	left ()
	"left" sub-node of the binary tree

const BinaryTree *	left () const
	"left" sub-node of the binary tree

BinaryTree *	right ()
	"right" sub-node of the binary tree

const BinaryTree *	right () const
	"right" sub-node of the binary tree

std::size_t	size () const
	number of points inside the space represented by this node

std::size_t	nodes () const
	number of sub-nodes in this tree (including the node itself)

std::size_t	index (std::size_t point) const

double	distanceFromPlane (value_type const &point) const
	Function describing the separation of space.

double	threshold () const
	Separation threshold.

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.

virtual double	squaredDistanceLowerBound (value_type const &point) const =0
	Compute lower bound on the squared distance to the space cell.

Protected Member Functions
	LCTree (LCTree parent, std::size_t list, std::size_t size)
	(internal) construction of a non-root node

template<class Range >
void	buildTree (TreeConstruction tc, Range &points)

double	funct (VectorType const &reference) const
	function describing the separating hyperplane

template<class Range >
void	calculateNormal (Range const &samples)

Protected Member Functions inherited from shark::BinaryTree< InputT >
	BinaryTree (BinaryTree parent, std::size_t list, std::size_t size)
	Sub-node constructor.

virtual double	funct (value_type const &point) const =0
	Function describing the separation of space.

template<class Range1 , class Range2 >
Range2::iterator	splitList (Range1 &values, Range2 &points)
	Split the data in the point list and calculate the treshold accordingly.

Protected Attributes
VectorType	m_normal
	split/cut normal vector of this node

BinaryTree *	mep_parent
	parent node

BinaryTree *	mp_left
	"left" child node

BinaryTree *	mp_right
	"right" child node

std::size_t *	mp_indexList
	list of indices to points in the dataset

std::size_t	m_size
	number of points in this node

std::size_t	m_nodes
	number of nodes in the sub-tree represented by this node

Protected Attributes inherited from shark::BinaryTree< InputT >
BinaryTree *	mep_parent
	parent node

BinaryTree *	mp_left
	"left" child node

BinaryTree *	mp_right
	"right" child node

std::size_t *	mp_indexList
	list of indices to points in the dataset

std::size_t	m_size
	number of points in this node

std::size_t	m_nodes
	number of nodes in the sub-tree represented by this node

double	m_threshold
	threshold for the separating function

Detailed Description

template<class VectorType = RealVector, int CuttingAccuracy = 25>
class shark::LCTree< VectorType, CuttingAccuracy >

LC-tree, a binary space-partitioning tree.

: LC-tree data structure for efficient nearest neighbor searches in possibly high-dimensional spaces, but with low-dimensional effective data dimension (means << 10 dimensions). "LC" stands for Linear Cut.

This tree requires the existence of a function inner_prod computing the standard inner product of two objects of type VectorType, and a function distanceSqr computing the squared Euclidean distance between two vectors.

: The tree is constructed from data by splitting the direction with largest extent (in the data covered, not space represented by the cell), recursively. Approximate direction and median are used to determine the cutting hyperplane, where the maximal number of points used to estimate the median can be controlled with the template parameter CuttingAccuracy.

: The bucket size for the tree is always one, such that there is a unique point in each leaf cell.

Definition at line 80 of file LCTree.h.

Constructor & Destructor Documentation

◆ LCTree() [1/2]

template<class VectorType = RealVector, int CuttingAccuracy = 25>

shark::LCTree< VectorType, CuttingAccuracy >::LCTree	(	Data< RealVector > const &	dataset,
		TreeConstruction	tc = `TreeConstruction()`
	)

inline

Construct the tree from data. It is assumed that the container exceeds the lifetime of the LCTree (which holds only references to the points), and that the memory locations of the points remain unchanged.

Definition at line 90 of file LCTree.h.

References shark::LCTree< VectorType, CuttingAccuracy >::buildTree(), shark::LCTree< VectorType, CuttingAccuracy >::m_size, and shark::LCTree< VectorType, CuttingAccuracy >::mp_indexList.