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

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

Inheritance diagram for shark::KDTree< InputT >:

Public Member Functions
	KDTree (Data< InputT > const &dataset, TreeConstruction tc=TreeConstruction())

double	lower (std::size_t dim) const

double	upper (std::size_t dim) const

double	squaredDistanceLowerBound (InputT 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.

Protected Member Functions
	KDTree (KDTree 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)

template<class Range >
std::size_t	calculateCuttingDimension (Range const &points) const
	Calculate the dimension which should be cut by this node.

double	funct (InputT const &reference) const

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

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
std::size_t	m_cutDim
	split/cut dimension 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 InputT>
class shark::KDTree< InputT >

KD-tree, a binary space-partitioning tree.

: KD-tree data structure for efficient nearest neighbor searches in low-dimensional spaces. Low-dimensional means << 10 dimensions.

: The tree is constructed from data by splitting the dimension with largest extent (in the data covered, not space represented by the cell), recursively. An approximate median is used as the cutting point, where the maximal number of points used to estimate the median can be controlled with the template parameter MedianAccuracy.

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

Definition at line 71 of file KDTree.h.

Constructor & Destructor Documentation

◆ KDTree() [1/2]

template<class InputT >

shark::KDTree< InputT >::KDTree	(	Data< InputT > const &	dataset,
		TreeConstruction	tc = `TreeConstruction()`
	)

inline

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

Definition at line 83 of file KDTree.h.

References shark::KDTree< InputT >::buildTree(), shark::KDTree< InputT >::m_size, and shark::KDTree< InputT >::mp_indexList.

◆ KDTree() [2/2]

template<class InputT >

shark::KDTree< InputT >::KDTree	(	KDTree< InputT > *	parent,
		std::size_t *	list,
		std::size_t	size
	)

inlineprotected

(internal) construction of a non-root node

Definition at line 191 of file KDTree.h.

Member Function Documentation

◆ buildTree()

template<class InputT >

template<class Range >

void shark::KDTree< InputT >::buildTree	(	TreeConstruction	tc,
		Range &	points
	)

inlineprotected

(internal) construction method: median-cuts of the dimension with widest spread

Definition at line 199 of file KDTree.h.

References shark::KDTree< InputT >::calculateCuttingDimension(), shark::BinaryTree< InputT >::left(), shark::KDTree< InputT >::m_cutDim, shark::KDTree< InputT >::m_nodes, shark::KDTree< InputT >::m_size, shark::TreeConstruction::maxBucketSize(), shark::TreeConstruction::maxDepth(), shark::KDTree< InputT >::mp_indexList, shark::KDTree< InputT >::mp_left, shark::KDTree< InputT >::mp_right, shark::TreeConstruction::nextDepthLevel(), shark::BinaryTree< InputT >::nodes(), shark::BinaryTree< InputT >::right(), and shark::BinaryTree< InputT >::splitList().

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

◆ calculateCuttingDimension()

template<class InputT >

template<class Range >

std::size_t shark::KDTree< InputT >::calculateCuttingDimension ( Range const & points ) const

inlineprotected

Calculate the dimension which should be cut by this node.

The KD-Tree calculates the Axis-Aligned-Bounding-Box surrounding the points and splits the longest dimension

Definition at line 244 of file KDTree.h.

References shark::KDTree< InputT >::m_size.

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

◆ funct()

template<class InputT >

double shark::KDTree< InputT >::funct ( InputT const & reference ) const

inlineprotectedvirtual

Function describing the separating hyperplane as its zero set. It is guaranteed that the gradient has norm one, thus the absolute value of the function indicates distance from the hyperplane.

Implements shark::BinaryTree< InputT >.

Definition at line 286 of file KDTree.h.

References shark::KDTree< InputT >::m_cutDim.

◆ lower()

template<class InputT >

double shark::KDTree< InputT >::lower ( std::size_t dim ) const

inline

lower bound on the box-shaped space represented by this cell

Definition at line 104 of file KDTree.h.

References shark::KDTree< InputT >::mep_parent, shark::BinaryTree< InputT >::mp_right, shark::BinaryTree< InputT >::parent(), and shark::BinaryTree< InputT >::threshold().

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

◆ squaredDistanceLowerBound()

template<class InputT >

double shark::KDTree< InputT >::squaredDistanceLowerBound ( InputT const & reference ) const

inlinevirtual

: Compute the squared Euclidean distance of this cell to the given reference point, or alternatively a lower bound on this value.

: In the case of the kd-tree the computation is exact, however, only a lower bound is required in general, and other space partitioning trees used in the future may only be able to provide a lower bound, at least with reasonable computational efforts.

Implements shark::BinaryTree< InputT >.

Definition at line 138 of file KDTree.h.

References shark::KDTree< InputT >::lower(), shark::sqr(), and shark::KDTree< InputT >::upper().

◆ upper()

template<class InputT >

double shark::KDTree< InputT >::upper ( std::size_t dim ) const

template<class InputT >

BinaryTree* shark::BinaryTree< InputT >::mp_right

protected

"right" child node

Definition at line 352 of file BinaryTree.h.

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

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

include/shark/Models/Trees/KDTree.h

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ KDTree() [1/2]

◆ KDTree() [2/2]

Member Function Documentation

◆ buildTree()

◆ calculateCuttingDimension()

◆ funct()

◆ lower()

◆ squaredDistanceLowerBound()

◆ upper()

Member Data Documentation

◆ m_cutDim

◆ m_nodes

◆ m_size

◆ mep_parent

◆ mp_indexList

◆ mp_left

◆ mp_right