#include <kmeans_index.h>
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 |
![]() | |
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 > ¢ers) |
flann_algorithm_t | getType () const |
void | initCenterChooser () |
KMeansIndex (const IndexParams ¶ms=KMeansIndexParams(), Distance d=Distance()) | |
KMeansIndex (const KMeansIndex &other) | |
KMeansIndex (const Matrix< ElementType > &inputData, const IndexParams ¶ms=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 () |
![]() | |
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 ¶ms) 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 ¶ms) 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 ¶ms) const |
Perform k-nearest neighbor search. More... | |
NNIndex (const IndexParams ¶ms, 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 ¶ms) const |
virtual int | radiusSearch (const Matrix< ElementType > &queries, Matrix< size_t > &indices, Matrix< DistanceType > &dists, float radius, const SearchParams ¶ms) 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 ¶ms) 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 ¶ms) 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 () |
![]() | |
virtual | ~IndexBase () |
Protected Member Functions | |
void | buildIndexImpl () |
![]() | |
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 | |
![]() | |
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_ |
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.
typedef NNIndex<Distance> rtflann::KMeansIndex< Distance >::BaseClass |
Definition at line 117 of file kmeans_index.h.
|
private |
Alias definition for a nicer syntax.
Definition at line 482 of file kmeans_index.h.
typedef Distance::ResultType rtflann::KMeansIndex< Distance >::DistanceType |
Definition at line 115 of file kmeans_index.h.
typedef Distance::ElementType rtflann::KMeansIndex< Distance >::ElementType |
Definition at line 114 of file kmeans_index.h.
typedef bool rtflann::KMeansIndex< Distance >::needs_vector_space_distance |
Definition at line 119 of file kmeans_index.h.
|
private |
Definition at line 477 of file kmeans_index.h.
|
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.
|
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.
|
inline |
Definition at line 174 of file kmeans_index.h.
|
inlinevirtual |
Index destructor.
Release the memory used by the index.
Definition at line 215 of file kmeans_index.h.
|
inlinevirtual |
Incrementally add points to the index.
points | Matrix with points to be added |
rebuild_threshold |
Reimplemented from rtflann::NNIndex< Distance >.
Definition at line 243 of file kmeans_index.h.
|
inlineprivate |
Definition at line 997 of file kmeans_index.h.
|
inline |
Builds the index
Definition at line 153 of file nn_index.h.
|
inline |
Builds the index using the specified dataset
dataset | the dataset to use |
Definition at line 169 of file nn_index.h.
|
inlineprotectedvirtual |
Builds the index
Implements rtflann::NNIndex< Distance >.
Definition at line 357 of file kmeans_index.h.
|
inlinevirtual |
Implements rtflann::NNIndex< Distance >.
Definition at line 221 of file kmeans_index.h.
|
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.
|
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.
|
inlineprivate |
Definition at line 495 of file kmeans_index.h.
|
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.
|
inlineprivate |
Function the performs exact nearest neighbor search by traversing the entire tree.
Definition at line 863 of file kmeans_index.h.
|
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.
|
inlineprivate |
Definition at line 743 of file kmeans_index.h.
|
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.
|
inlineprivatevirtual |
Helper function
Implements rtflann::NNIndex< Distance >.
Definition at line 488 of file kmeans_index.h.
|
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.
|
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.
|
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.
|
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.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 123 of file kmeans_index.h.
|
inline |
Definition at line 193 of file kmeans_index.h.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 294 of file kmeans_index.h.
|
inline |
Definition at line 186 of file kmeans_index.h.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 288 of file kmeans_index.h.
|
inline |
Definition at line 262 of file kmeans_index.h.
|
inline |
Definition at line 227 of file kmeans_index.h.
|
inlineprivate |
Definition at line 1038 of file kmeans_index.h.
|
inlinevirtual |
Computes the inde memory usage Returns: memory used by the index
Implements rtflann::IndexBase.
Definition at line 236 of file kmeans_index.h.
|
private |
The branching factor used in the hierarchical k-means clustering
Definition at line 1053 of file kmeans_index.h.
|
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.
|
private |
Algorithm for choosing the cluster centers
Definition at line 1059 of file kmeans_index.h.
|
private |
Algorithm used to choose initial centers
Definition at line 1087 of file kmeans_index.h.
|
private |
Maximum number of iterations to use when performing k-means clustering
Definition at line 1056 of file kmeans_index.h.
|
private |
Memory occupied by the index.
Definition at line 1082 of file kmeans_index.h.
|
private |
Pooled memory allocator.
Definition at line 1077 of file kmeans_index.h.
|
private |
The root node in the tree.
Definition at line 1072 of file kmeans_index.h.