rtflann::KMeansIndex< Distance > Class Template Reference

#include <kmeans_index.h>

Inheritance diagram for rtflann::KMeansIndex< Distance >:

Classes
struct	Node
struct	PointInfo

Public Types
typedef NNIndex< Distance >	BaseClass
typedef Distance::ResultType	DistanceType
typedef Distance::ElementType	ElementType
typedef bool	needs_vector_space_distance
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...
virtual void	buildIndex ()
virtual void	buildIndex (const Matrix< ElementType > &dataset)
BaseClass *	clone () const
void	findNeighbors (ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams) const
int	getClusterCenters (Matrix< DistanceType > &centers)
flann_algorithm_t	getType () const
void	initCenterChooser ()
	KMeansIndex (const IndexParams &params=KMeansIndexParams(), Distance d=Distance())
	KMeansIndex (const KMeansIndex &other)
	KMeansIndex (const Matrix< ElementType > &inputData, const IndexParams &params=KMeansIndexParams(), Distance d=Distance())
void	loadIndex (FILE *stream)
KMeansIndex &	operator= (KMeansIndex other)
void	saveIndex (FILE *stream)
template<typename Archive >
void	serialize (Archive &ar)
void	set_cb_index (float index)
int	usedMemory () const
virtual	~KMeansIndex ()
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...
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
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...
	NNIndex (const IndexParams &params, Distance d)
	NNIndex (const NNIndex &other)
	NNIndex (Distance d)
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, Matrix< size_t > &indices, Matrix< 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
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...
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, DistanceType dist_to_pivot)
void	computeClustering (NodePtr node, int *indices, int indices_length, int branching)
void	computeNodeStatistics (NodePtr node, const std::vector< int > &indices)
void	copyTree (NodePtr &dst, const NodePtr &src)
int	exploreNodeBranches (NodePtr node, const ElementType *q, Heap< BranchSt > *heap) const
template<bool with_removed>
void	findExactNN (NodePtr node, ResultSet< DistanceType > &result, const ElementType *vec) const
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) const
void	freeIndex ()
void	getCenterOrdering (NodePtr node, const ElementType *q, std::vector< int > &sort_indices) const
DistanceType	getDistanceToBorder (DistanceType *p, DistanceType *c, DistanceType *q) const
int	getMinVarianceClusters (NodePtr root, std::vector< NodePtr > &clusters, int clusters_length, DistanceType &varianceValue) const
void	swap (KMeansIndex &other)

Private Attributes
int	branching_
float	cb_index_
flann_centers_init_t	centers_init_
CenterChooser< Distance > *	chooseCenters_
int	iterations_
int	memoryCounter_
PooledAllocator	pool_
NodePtr	root_

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::KMeansIndex< Distance >

Hierarchical kmeans index

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

Definition at line 111 of file kmeans_index.h.

Member Typedef Documentation

BaseClass

template<typename Distance >

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

Definition at line 117 of file kmeans_index.h.

BranchSt

template<typename Distance >

typedef BranchStruct<NodePtr, DistanceType> rtflann::KMeansIndex< Distance >::BranchSt

private

Alias definition for a nicer syntax.

Definition at line 482 of file kmeans_index.h.

DistanceType

template<typename Distance >

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

Definition at line 115 of file kmeans_index.h.

ElementType

template<typename Distance >

typedef Distance::ElementType rtflann::KMeansIndex< Distance >::ElementType

Definition at line 114 of file kmeans_index.h.

needs_vector_space_distance

template<typename Distance >

typedef bool rtflann::KMeansIndex< Distance >::needs_vector_space_distance

Definition at line 119 of file kmeans_index.h.

NodePtr

template<typename Distance >

typedef Node* rtflann::KMeansIndex< Distance >::NodePtr

private

Definition at line 477 of file kmeans_index.h.

Constructor & Destructor Documentation

KMeansIndex() [1/3]

template<typename Distance >

rtflann::KMeansIndex< Distance >::KMeansIndex ( const Matrix< ElementType > &  inputData, const IndexParams &  params = KMeansIndexParams(), 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 135 of file kmeans_index.h.

KMeansIndex() [2/3]

template<typename Distance >

rtflann::KMeansIndex< Distance >::KMeansIndex ( const IndexParams &  params = KMeansIndexParams(), 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 159 of file kmeans_index.h.

KMeansIndex() [3/3]

template<typename Distance >

rtflann::KMeansIndex< Distance >::KMeansIndex ( const KMeansIndex< Distance > &  other )

inline

Definition at line 174 of file kmeans_index.h.

~KMeansIndex()

template<typename Distance >

virtual rtflann::KMeansIndex< Distance >::~KMeansIndex ( )

inlinevirtual

Index destructor.

Release the memory used by the index.

Definition at line 215 of file kmeans_index.h.

Member Function Documentation

addPoints()

template<typename Distance >

void rtflann::KMeansIndex< 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 243 of file kmeans_index.h.

addPointToTree()

template<typename Distance >

void rtflann::KMeansIndex< Distance >::addPointToTree ( NodePtr  node, size_t  index, DistanceType  dist_to_pivot  )

inlineprivate

Definition at line 997 of file kmeans_index.h.

buildIndex() [1/2]

template<typename Distance >

virtual void rtflann::NNIndex< Distance >::buildIndex

inline

Builds the index

Definition at line 153 of file nn_index.h.

buildIndex() [2/2]

template<typename Distance >

virtual void rtflann::NNIndex< Distance >::buildIndex

inline

Builds the index using the specified dataset

Parameters

dataset

the dataset to use

Definition at line 169 of file nn_index.h.

buildIndexImpl()

template<typename Distance >

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

inlineprotectedvirtual

Builds the index

Implements rtflann::NNIndex< Distance >.

Definition at line 357 of file kmeans_index.h.

clone()

template<typename Distance >

BaseClass* rtflann::KMeansIndex< Distance >::clone ( ) const

inlinevirtual

Implements rtflann::NNIndex< Distance >.

Definition at line 221 of file kmeans_index.h.

computeClustering()

template<typename Distance >

void rtflann::KMeansIndex< Distance >::computeClustering ( NodePtr  node, int *  indices, int  indices_length, int  branching  )

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

TODO: for 1-sized clusters don't store a cluster center (it's the same as the single cluster point)

Definition at line 570 of file kmeans_index.h.

computeNodeStatistics()

template<typename Distance >

void rtflann::KMeansIndex< Distance >::computeNodeStatistics ( NodePtr  node, const std::vector< int > &  indices  )

inlineprivate

Computes the statistics of a node (mean, radius, variance).

Params: node = the node to use indices = the indices of the points belonging to the node

Definition at line 523 of file kmeans_index.h.

copyTree()

template<typename Distance >

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

inlineprivate

Definition at line 495 of file kmeans_index.h.

exploreNodeBranches()

template<typename Distance >

int rtflann::KMeansIndex< Distance >::exploreNodeBranches ( NodePtr  node, const ElementType *  q, Heap< BranchSt > *  heap  ) const

inlineprivate

Helper function that computes the nearest childs of a node to a given query point. Params: node = the node q = the query point distances = array with the distances to each child node. Returns:

Definition at line 830 of file kmeans_index.h.

findExactNN()

template<typename Distance >

template<bool with_removed>

void rtflann::KMeansIndex< Distance >::findExactNN ( NodePtr  node, ResultSet< DistanceType > &  result, const ElementType *  vec  ) const

inlineprivate

Function the performs exact nearest neighbor search by traversing the entire tree.

Definition at line 863 of file kmeans_index.h.

findNeighbors()

template<typename Distance >

void rtflann::KMeansIndex< 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, cb_index)

Implements rtflann::NNIndex< Distance >.

Definition at line 311 of file kmeans_index.h.

findNeighborsWithRemoved()

template<typename Distance >

template<bool with_removed>

void rtflann::KMeansIndex< Distance >::findNeighborsWithRemoved ( ResultSet< DistanceType > &  result, const ElementType *  vec, const SearchParams &  searchParams  ) const

inlineprivate

Definition at line 743 of file kmeans_index.h.

findNN()

template<typename Distance >

template<bool with_removed>

void rtflann::KMeansIndex< Distance >::findNN ( NodePtr  node, ResultSet< DistanceType > &  result, const ElementType *  vec, int &  checks, int  maxChecks, Heap< BranchSt > *  heap  ) 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 783 of file kmeans_index.h.

freeIndex()

template<typename Distance >

void rtflann::KMeansIndex< Distance >::freeIndex ( )

inlineprivatevirtual

Helper function

Implements rtflann::NNIndex< Distance >.

Definition at line 488 of file kmeans_index.h.

getCenterOrdering()

template<typename Distance >

void rtflann::KMeansIndex< Distance >::getCenterOrdering ( NodePtr  node, const ElementType *  q, std::vector< int > &  sort_indices  ) const

inlineprivate

Helper function.

I computes the order in which to traverse the child nodes of a particular node.

Definition at line 908 of file kmeans_index.h.

getClusterCenters()

template<typename Distance >

int rtflann::KMeansIndex< Distance >::getClusterCenters ( Matrix< DistanceType > &  centers )

inline

Clustering function that takes a cut in the hierarchical k-means tree and return the clusters centers of that clustering. Params: numClusters = number of clusters to have in the clustering computed Returns: number of cluster centers

Definition at line 329 of file kmeans_index.h.

getDistanceToBorder()

template<typename Distance >

DistanceType rtflann::KMeansIndex< Distance >::getDistanceToBorder ( DistanceType *  p, DistanceType *  c, DistanceType *  q  ) const

inlineprivate

Method that computes the squared distance from the query point q from inside region with center c to the border between this region and the region with center p

Definition at line 930 of file kmeans_index.h.

getMinVarianceClusters()

template<typename Distance >

int rtflann::KMeansIndex< Distance >::getMinVarianceClusters ( NodePtr  root, std::vector< NodePtr > &  clusters, int  clusters_length, DistanceType &  varianceValue  ) const

inlineprivate

Helper function the descends in the hierarchical k-means tree by spliting those clusters that minimize the overall variance of the clustering. Params: root = root node clusters = array with clusters centers (return value) varianceValue = variance of the clustering (return value) Returns:

Definition at line 954 of file kmeans_index.h.

getType()

template<typename Distance >

flann_algorithm_t rtflann::KMeansIndex< Distance >::getType ( ) const

inlinevirtual

Implements rtflann::IndexBase.

Definition at line 123 of file kmeans_index.h.

initCenterChooser()

template<typename Distance >

void rtflann::KMeansIndex< Distance >::initCenterChooser ( )

inline

Definition at line 193 of file kmeans_index.h.

loadIndex()

template<typename Distance >

void rtflann::KMeansIndex< Distance >::loadIndex ( FILE *  stream )

inlinevirtual

Implements rtflann::IndexBase.

Definition at line 294 of file kmeans_index.h.

operator=()

template<typename Distance >

KMeansIndex& rtflann::KMeansIndex< Distance >::operator= ( KMeansIndex< Distance >  other )

inline

Definition at line 186 of file kmeans_index.h.

saveIndex()

template<typename Distance >

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

inlinevirtual

Implements rtflann::IndexBase.

Definition at line 288 of file kmeans_index.h.

serialize()

template<typename Distance >

template<typename Archive >

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

inline

Definition at line 262 of file kmeans_index.h.

set_cb_index()

template<typename Distance >

void rtflann::KMeansIndex< Distance >::set_cb_index ( float  index )

inline

Definition at line 227 of file kmeans_index.h.

swap()

template<typename Distance >

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

inlineprivate

Definition at line 1038 of file kmeans_index.h.

usedMemory()

template<typename Distance >

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

inlinevirtual

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

Implements rtflann::IndexBase.

Definition at line 236 of file kmeans_index.h.

Member Data Documentation

branching_

template<typename Distance >

int rtflann::KMeansIndex< Distance >::branching_

private

The branching factor used in the hierarchical k-means clustering

Definition at line 1053 of file kmeans_index.h.

cb_index_

template<typename Distance >

float rtflann::KMeansIndex< Distance >::cb_index_

private

Cluster border index. This is used in the tree search phase when determining the closest cluster to explore next. A zero value takes into account only the cluster centres, a value greater then zero also take into account the size of the cluster.

Definition at line 1067 of file kmeans_index.h.

centers_init_

template<typename Distance >

flann_centers_init_t rtflann::KMeansIndex< Distance >::centers_init_

private

Algorithm for choosing the cluster centers

Definition at line 1059 of file kmeans_index.h.

chooseCenters_

template<typename Distance >

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

private

Algorithm used to choose initial centers

Definition at line 1087 of file kmeans_index.h.

iterations_

template<typename Distance >

int rtflann::KMeansIndex< Distance >::iterations_

private

Maximum number of iterations to use when performing k-means clustering

Definition at line 1056 of file kmeans_index.h.

memoryCounter_

template<typename Distance >

int rtflann::KMeansIndex< Distance >::memoryCounter_

private

Memory occupied by the index.

Definition at line 1082 of file kmeans_index.h.

pool_

template<typename Distance >

PooledAllocator rtflann::KMeansIndex< Distance >::pool_

private

Pooled memory allocator.

Definition at line 1077 of file kmeans_index.h.

root_

template<typename Distance >

NodePtr rtflann::KMeansIndex< Distance >::root_

private

The root node in the tree.

Definition at line 1072 of file kmeans_index.h.

---

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

• kmeans_index.h