#include <hierarchical_clustering_index.h>

Inheritance diagram for rtflann::HierarchicalClusteringIndex< Distance >:

Classes
struct	Node
struct	PointInfo
Public Types
typedef NNIndex< Distance >	BaseClass
typedef Distance::ResultType	DistanceType
typedef Distance::ElementType	ElementType
Public Member Functions
void	addPoints (const Matrix< ElementType > &points, float rebuild_threshold=2)
	Incrementally add points to the index.
BaseClass *	clone () const
void	findNeighbors (ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams) const
flann_algorithm_t	getType () const
	HierarchicalClusteringIndex (const IndexParams &index_params=HierarchicalClusteringIndexParams(), Distance d=Distance())
	HierarchicalClusteringIndex (const Matrix< ElementType > &inputData, const IndexParams &index_params=HierarchicalClusteringIndexParams(), Distance d=Distance())
	HierarchicalClusteringIndex (const HierarchicalClusteringIndex &other)
void	initCenterChooser ()
void	loadIndex (FILE *stream)
HierarchicalClusteringIndex &	operator= (HierarchicalClusteringIndex other)
void	saveIndex (FILE *stream)
template<typename Archive >
void	serialize (Archive &ar)
int	usedMemory () const
virtual	~HierarchicalClusteringIndex ()
Protected Member Functions
void	buildIndexImpl ()
Private Types
typedef BranchStruct< NodePtr, DistanceType >	BranchSt
typedef Node *	NodePtr
Private Member Functions
void	addPointToTree (NodePtr node, size_t index)
void	computeClustering (NodePtr node, int *indices, int indices_length)
void	computeLabels (int indices, int indices_length, int centers, int centers_length, int *labels, DistanceType &cost)
void	copyTree (NodePtr &dst, const NodePtr &src)
template<bool with_removed>
void	findNeighborsWithRemoved (ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams) const
template<bool with_removed>
void	findNN (NodePtr node, ResultSet< DistanceType > &result, const ElementType vec, int &checks, int maxChecks, Heap< BranchSt > heap, DynamicBitset &checked) const
void	freeIndex ()
void	swap (HierarchicalClusteringIndex &other)
Private Attributes
int	branching_
flann_centers_init_t	centers_init_
CenterChooser< Distance > *	chooseCenters_
int	leaf_max_size_
int	memoryCounter_
PooledAllocator	pool_
std::vector< Node * >	tree_roots_
int	trees_

Detailed Description

template<typename Distance>
class rtflann::HierarchicalClusteringIndex< Distance >

Hierarchical index

Contains a tree constructed through a hierarchical clustering and other information for indexing a set of points for nearest-neighbour matching.

Definition at line 86 of file hierarchical_clustering_index.h.

Member Typedef Documentation

template<typename Distance >

typedef NNIndex<Distance> rtflann::HierarchicalClusteringIndex< Distance >::BaseClass

Definition at line 92 of file hierarchical_clustering_index.h.

template<typename Distance >

typedef BranchStruct<NodePtr, DistanceType> rtflann::HierarchicalClusteringIndex< Distance >::BranchSt [private]

Alias definition for a nicer syntax.

Definition at line 429 of file hierarchical_clustering_index.h.

template<typename Distance >

typedef Distance::ResultType rtflann::HierarchicalClusteringIndex< Distance >::DistanceType

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 90 of file hierarchical_clustering_index.h.

template<typename Distance >

typedef Distance::ElementType rtflann::HierarchicalClusteringIndex< Distance >::ElementType

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 89 of file hierarchical_clustering_index.h.

template<typename Distance >

typedef Node* rtflann::HierarchicalClusteringIndex< Distance >::NodePtr [private]

Definition at line 422 of file hierarchical_clustering_index.h.

Constructor & Destructor Documentation

template<typename Distance >

rtflann::HierarchicalClusteringIndex< Distance >::HierarchicalClusteringIndex	(	const IndexParams &	index_params = `HierarchicalClusteringIndexParams()`,
		Distance	d = `Distance()`
	)		`[inline]`

Constructor.

Parameters:

index_params
d

Definition at line 100 of file hierarchical_clustering_index.h.

template<typename Distance >

rtflann::HierarchicalClusteringIndex< Distance >::HierarchicalClusteringIndex	(	const Matrix< ElementType > &	inputData,
		const IndexParams &	index_params = `HierarchicalClusteringIndexParams()`,
		Distance	d = `Distance()`
	)		`[inline]`

Index constructor

Params: inputData = dataset with the input features params = parameters passed to the hierarchical k-means algorithm

Definition at line 121 of file hierarchical_clustering_index.h.

template<typename Distance >

rtflann::HierarchicalClusteringIndex< Distance >::HierarchicalClusteringIndex ( const HierarchicalClusteringIndex< Distance > & other ) [inline]

Definition at line 140 of file hierarchical_clustering_index.h.

template<typename Distance >

virtual rtflann::HierarchicalClusteringIndex< Distance >::~HierarchicalClusteringIndex ( ) [inline, virtual]

Index destructor.

Release the memory used by the index.

Definition at line 187 of file hierarchical_clustering_index.h.

Member Function Documentation

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::addPoints	(	const Matrix< ElementType > &	points,
		float	rebuild_threshold = `2`
	)		`[inline, virtual]`

Incrementally add points to the index.

Parameters:

points	Matrix with points to be added
rebuild_threshold

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 209 of file hierarchical_clustering_index.h.

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::addPointToTree	(	NodePtr	node,
		size_t	index
	)		`[inline, private]`

Definition at line 622 of file hierarchical_clustering_index.h.

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::buildIndexImpl ( ) [inline, protected, virtual]

Builds the index

Implements rtflann::NNIndex< Distance >.

Definition at line 305 of file hierarchical_clustering_index.h.

template<typename Distance >

BaseClass* rtflann::HierarchicalClusteringIndex< Distance >::clone ( ) const [inline, virtual]

Implements rtflann::NNIndex< Distance >.

Definition at line 193 of file hierarchical_clustering_index.h.

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::computeClustering	(	NodePtr	node,
		int *	indices,
		int	indices_length
	)		`[inline, private]`

The method responsible with actually doing the recursive hierarchical clustering

Params: node = the node to cluster indices = indices of the points belonging to the current node branching = the branching factor to use in the clustering

Definition at line 490 of file hierarchical_clustering_index.h.

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::computeLabels	(	int *	indices,
		int	indices_length,
		int *	centers,
		int	centers_length,
		int *	labels,
		DistanceType &	cost
	)		`[inline, private]`

Definition at line 462 of file hierarchical_clustering_index.h.

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::copyTree	(	NodePtr &	dst,
		const NodePtr &	src
	)		`[inline, private]`

Definition at line 443 of file hierarchical_clustering_index.h.

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::findNeighbors	(	ResultSet< DistanceType > &	result,
		const ElementType *	vec,
		const SearchParams &	searchParams
	)		const `[inline, virtual]`

Find set of nearest neighbors to vec. Their indices are stored inside the result object.

Params: result = the result object in which the indices of the nearest-neighbors are stored vec = the vector for which to search the nearest neighbors searchParams = parameters that influence the search algorithm (checks)

Implements rtflann::NNIndex< Distance >.

Definition at line 290 of file hierarchical_clustering_index.h.

template<typename Distance >

template<bool with_removed>

void rtflann::HierarchicalClusteringIndex< Distance >::findNeighborsWithRemoved	(	ResultSet< DistanceType > &	result,
		const ElementType *	vec,
		const SearchParams &	searchParams
	)		const `[inline, private]`

Definition at line 546 of file hierarchical_clustering_index.h.

template<typename Distance >

template<bool with_removed>

void rtflann::HierarchicalClusteringIndex< Distance >::findNN	(	NodePtr	node,
		ResultSet< DistanceType > &	result,
		const ElementType *	vec,
		int &	checks,
		int	maxChecks,
		Heap< BranchSt > *	heap,
		DynamicBitset &	checked
	)		const `[inline, private]`

Performs one descent in the hierarchical k-means tree. The branches not visited are stored in a priority queue.

Params: node = node to explore result = container for the k-nearest neighbors found vec = query points checks = how many points in the dataset have been checked so far maxChecks = maximum dataset points to checks

Definition at line 582 of file hierarchical_clustering_index.h.

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::freeIndex ( ) [inline, private, virtual]

Clears Node tree calling Node destructor explicitly

Implements rtflann::NNIndex< Distance >.

Definition at line 436 of file hierarchical_clustering_index.h.

template<typename Distance >

flann_algorithm_t rtflann::HierarchicalClusteringIndex< Distance >::getType ( ) const [inline, virtual]

Implements rtflann::IndexBase.

Definition at line 229 of file hierarchical_clustering_index.h.

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::initCenterChooser ( ) [inline]

Definition at line 162 of file hierarchical_clustering_index.h.

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::loadIndex ( FILE * stream ) [inline, virtual]

Implements rtflann::IndexBase.

Definition at line 273 of file hierarchical_clustering_index.h.

template<typename Distance >

HierarchicalClusteringIndex& rtflann::HierarchicalClusteringIndex< Distance >::operator= ( HierarchicalClusteringIndex< Distance > other ) [inline]