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< VectorType > | |
| 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... | |
| BinaryTree * | parent () |
| parent node More... | |
| const BinaryTree * | parent () const |
| parent node More... | |
| bool | hasChildren () const |
| bool | isLeaf () const |
| BinaryTree * | left () |
| "left" sub-node of the binary tree More... | |
| const BinaryTree * | left () const |
| "left" sub-node of the binary tree More... | |
| BinaryTree * | right () |
| "right" sub-node of the binary tree More... | |
| const BinaryTree * | right () 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 | |
| LCTree (LCTree *parent, std::size_t *list, std::size_t size) | |
| (internal) construction of a non-root node More... | |
| template<class Range > | |
| void | buildTree (TreeConstruction tc, Range &points) |
| double | funct (VectorType const &reference) const |
| function describing the separating hyperplane More... | |
| template<class Range > | |
| void | calculateNormal (Range const &samples) |
| Protected Member Functions inherited from shark::BinaryTree< VectorType > | |
| 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... | |
| Range2::iterator | splitList (Range1 &values, Range2 &points) |
| Split the data in the point list and calculate the treshold accordingly. More... | |
Protected Attributes | |
| VectorType | m_normal |
| split/cut normal vector of this node More... | |
| Protected Attributes inherited from shark::BinaryTree< VectorType > | |
| BinaryTree * | mep_parent |
| parent node More... | |
| BinaryTree * | mp_left |
| "left" child node More... | |
| BinaryTree * | mp_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 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.
Constructor & Destructor Documentation
◆ LCTree() [1/2]
|
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 89 of file LCTree.h.
References shark::LCTree< VectorType, CuttingAccuracy >::buildTree(), shark::BinaryTree< VectorType >::m_size, and shark::BinaryTree< VectorType >::mp_indexList.
◆ LCTree() [2/2]
|
inlineprotected |
Member Function Documentation
◆ buildTree()
|
inlineprotected |
(internal) construction method: median-cuts of the dimension with widest spread
Definition at line 145 of file LCTree.h.
References shark::LCTree< VectorType, CuttingAccuracy >::calculateNormal(), shark::BinaryTree< VectorType >::m_nodes, shark::BinaryTree< VectorType >::m_size, shark::TreeConstruction::maxBucketSize(), and shark::TreeConstruction::maxDepth().
Referenced by shark::LCTree< VectorType, CuttingAccuracy >::LCTree().
◆ calculateNormal()
|
inlineprotected |
Definition at line 206 of file LCTree.h.
Referenced by shark::LCTree< VectorType, CuttingAccuracy >::buildTree().
◆ funct()
|
inlineprotected |
◆ squaredDistanceLowerBound()
|
inline |
- Compute the squared Euclidean distance of this cell to the given reference point, or alternatively a lower bound on this value.
Definition at line 113 of file LCTree.h.
References shark::BinaryTree< InputT >::distanceFromPlane(), shark::BinaryTree< VectorType >::m_nodes, shark::BinaryTree< VectorType >::m_size, shark::BinaryTree< InputT >::mep_parent, shark::BinaryTree< VectorType >::mep_parent, shark::BinaryTree< VectorType >::mp_indexList, shark::BinaryTree< VectorType >::mp_left, shark::BinaryTree< VectorType >::mp_right, and shark::BinaryTree< InputT >::mp_right.
Member Data Documentation
◆ m_normal
|
protected |
The documentation for this class was generated from the following file:
- include/shark/Models/Trees/LCTree.h