#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 Types inherited from rtflann::NNIndex< Distance >
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. More...

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 ()

Public Member Functions inherited from rtflann::NNIndex< Distance >
virtual void	buildIndex ()

virtual void	buildIndex (const Matrix< ElementType > &dataset)

IndexParams	getParameters () const

virtual ElementType *	getPoint (size_t id)

virtual int	knnSearch (const Matrix< ElementType > &queries, Matrix< size_t > &indices, Matrix< DistanceType > &dists, size_t knn, const SearchParams &params) const
	Perform k-nearest neighbor search. More...

virtual int	knnSearch (const Matrix< ElementType > &queries, std::vector< std::vector< size_t > > &indices, std::vector< std::vector< DistanceType > > &dists, size_t knn, const SearchParams &params) const
	Perform k-nearest neighbor search. More...

int	knnSearch (const Matrix< ElementType > &queries, std::vector< std::vector< int > > &indices, std::vector< std::vector< DistanceType > > &dists, size_t knn, const SearchParams &params) const

	NNIndex (Distance d)

	NNIndex (const IndexParams &params, Distance d)

	NNIndex (const NNIndex &other)

virtual int	radiusSearch (const Matrix< ElementType > &queries, Matrix< size_t > &indices, Matrix< DistanceType > &dists, float radius, const SearchParams &params) const
	Perform radius search. More...

int	radiusSearch (const Matrix< ElementType > &queries, Matrix< int > &indices, Matrix< DistanceType > &dists, float radius, const SearchParams &params) const

virtual int	radiusSearch (const Matrix< ElementType > &queries, std::vector< std::vector< size_t > > &indices, std::vector< std::vector< DistanceType > > &dists, float radius, const SearchParams &params) const
	Perform radius search. More...

int	radiusSearch (const Matrix< ElementType > &queries, std::vector< std::vector< int > > &indices, std::vector< std::vector< DistanceType > > &dists, float radius, const SearchParams &params) const

size_t	removedCount () const

virtual void	removePoint (size_t id)

template<typename Archive >
void	serialize (Archive &ar)

size_t	size () const

size_t	sizeAtBuild () const

size_t	veclen () const

virtual	~NNIndex ()

Public Member Functions inherited from rtflann::IndexBase
virtual	~IndexBase ()

Protected Member Functions
void	buildIndexImpl ()

Protected Member Functions inherited from rtflann::NNIndex< Distance >
void	cleanRemovedPoints ()

void	extendDataset (const Matrix< ElementType > &new_points)

size_t	id_to_index (size_t id)

void	indices_to_ids (const size_t in, size_t out, size_t size) const

void	setDataset (const Matrix< ElementType > &dataset)

void	swap (NNIndex &other)

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_

Additional Inherited Members
Protected Attributes inherited from rtflann::NNIndex< Distance >
ElementType *	data_ptr_

Distance	distance_

std::vector< size_t >	ids_

IndexParams	index_params_

size_t	last_id_

std::vector< ElementType * >	points_

bool	removed_

size_t	removed_count_

DynamicBitset	removed_points_

size_t	size_

size_t	size_at_build_

size_t	veclen_

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

Definition at line 90 of file hierarchical_clustering_index.h.

template<typename Distance >

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

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 ( )

inlinevirtual

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`
	)

inlinevirtual

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
	)

inlineprivate

Definition at line 622 of file hierarchical_clustering_index.h.

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::buildIndexImpl ( )

inlineprotectedvirtual

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

inlinevirtual

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
	)

inlineprivate

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
	)

inlineprivate

Definition at line 462 of file hierarchical_clustering_index.h.

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::copyTree	(	NodePtr &	dst,
		const NodePtr &	src
	)

inlineprivate

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

inlinevirtual

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

inlineprivate

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

inlineprivate

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 ( )

inlineprivatevirtual

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

inlinevirtual

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 )

inlinevirtual

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

Definition at line 155 of file hierarchical_clustering_index.h.

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::saveIndex ( FILE * stream )

inlinevirtual

Implements rtflann::IndexBase.

Definition at line 266 of file hierarchical_clustering_index.h.

template<typename Distance >

template<typename Archive >

void rtflann::HierarchicalClusteringIndex< Distance >::serialize ( Archive & ar )

inline

Definition at line 236 of file hierarchical_clustering_index.h.

template<typename Distance >

void rtflann::HierarchicalClusteringIndex< Distance >::swap ( HierarchicalClusteringIndex< Distance > & other )

inlineprivate

Definition at line 658 of file hierarchical_clustering_index.h.

template<typename Distance >

int rtflann::HierarchicalClusteringIndex< Distance >::usedMemory ( ) const

inlinevirtual

Computes the inde memory usage Returns: memory used by the index

Implements rtflann::IndexBase.

Definition at line 202 of file hierarchical_clustering_index.h.

Member Data Documentation

template<typename Distance >

int rtflann::HierarchicalClusteringIndex< Distance >::branching_

private

index parameters Branching factor to use for clustering

Definition at line 697 of file hierarchical_clustering_index.h.

template<typename Distance >

flann_centers_init_t rtflann::HierarchicalClusteringIndex< Distance >::centers_init_

private

Algorithm to use for choosing cluster centers

Definition at line 707 of file hierarchical_clustering_index.h.

template<typename Distance >

CenterChooser<Distance>* rtflann::HierarchicalClusteringIndex< Distance >::chooseCenters_

private

Algorithm used to choose initial centers

Definition at line 717 of file hierarchical_clustering_index.h.

template<typename Distance >

int rtflann::HierarchicalClusteringIndex< Distance >::leaf_max_size_

private

Max size of leaf nodes

Definition at line 712 of file hierarchical_clustering_index.h.

template<typename Distance >

int rtflann::HierarchicalClusteringIndex< Distance >::memoryCounter_

private

Memory occupied by the index.

Definition at line 691 of file hierarchical_clustering_index.h.

template<typename Distance >

PooledAllocator rtflann::HierarchicalClusteringIndex< Distance >::pool_

private

Pooled memory allocator.

Using a pooled memory allocator is more efficient than allocating memory directly when there is a large number small of memory allocations.

Definition at line 686 of file hierarchical_clustering_index.h.

template<typename Distance >

std::vector<Node*> rtflann::HierarchicalClusteringIndex< Distance >::tree_roots_

private

The root nodes in the tree.

Definition at line 677 of file hierarchical_clustering_index.h.

template<typename Distance >

int rtflann::HierarchicalClusteringIndex< Distance >::trees_

private

How many parallel trees to build

Definition at line 702 of file hierarchical_clustering_index.h.

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

hierarchical_clustering_index.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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