#include <hierarchical_clustering_index.h>
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... | |
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 |
flann_algorithm_t | getType () const |
HierarchicalClusteringIndex (const HierarchicalClusteringIndex &other) | |
HierarchicalClusteringIndex (const IndexParams &index_params=HierarchicalClusteringIndexParams(), Distance d=Distance()) | |
HierarchicalClusteringIndex (const Matrix< ElementType > &inputData, const IndexParams &index_params=HierarchicalClusteringIndexParams(), Distance d=Distance()) | |
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 ¶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 () |
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_ |
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.
typedef NNIndex<Distance> rtflann::HierarchicalClusteringIndex< Distance >::BaseClass |
Definition at line 92 of file hierarchical_clustering_index.h.
|
private |
Alias definition for a nicer syntax.
Definition at line 429 of file hierarchical_clustering_index.h.
typedef Distance::ResultType rtflann::HierarchicalClusteringIndex< Distance >::DistanceType |
Definition at line 90 of file hierarchical_clustering_index.h.
typedef Distance::ElementType rtflann::HierarchicalClusteringIndex< Distance >::ElementType |
Definition at line 89 of file hierarchical_clustering_index.h.
|
private |
Definition at line 422 of file hierarchical_clustering_index.h.
|
inline |
Constructor.
index_params | |
d |
Definition at line 100 of file hierarchical_clustering_index.h.
|
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.
|
inline |
Definition at line 140 of file hierarchical_clustering_index.h.
|
inlinevirtual |
Index destructor.
Release the memory used by the index.
Definition at line 187 of file hierarchical_clustering_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 209 of file hierarchical_clustering_index.h.
|
inlineprivate |
Definition at line 622 of file hierarchical_clustering_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 305 of file hierarchical_clustering_index.h.
|
inlinevirtual |
Implements rtflann::NNIndex< Distance >.
Definition at line 193 of file hierarchical_clustering_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
Definition at line 490 of file hierarchical_clustering_index.h.
|
inlineprivate |
Definition at line 462 of file hierarchical_clustering_index.h.
|
inlineprivate |
Definition at line 443 of file hierarchical_clustering_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)
Implements rtflann::NNIndex< Distance >.
Definition at line 290 of file hierarchical_clustering_index.h.
|
inlineprivate |
Definition at line 546 of file hierarchical_clustering_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 582 of file hierarchical_clustering_index.h.
|
inlineprivatevirtual |
Clears Node tree calling Node destructor explicitly
Implements rtflann::NNIndex< Distance >.
Definition at line 436 of file hierarchical_clustering_index.h.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 229 of file hierarchical_clustering_index.h.
|
inline |
Definition at line 162 of file hierarchical_clustering_index.h.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 273 of file hierarchical_clustering_index.h.
|
inline |
Definition at line 155 of file hierarchical_clustering_index.h.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 266 of file hierarchical_clustering_index.h.
|
inline |
Definition at line 236 of file hierarchical_clustering_index.h.
|
inlineprivate |
Definition at line 658 of file hierarchical_clustering_index.h.
|
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.
|
private |
index parameters Branching factor to use for clustering
Definition at line 697 of file hierarchical_clustering_index.h.
|
private |
Algorithm to use for choosing cluster centers
Definition at line 707 of file hierarchical_clustering_index.h.
|
private |
Algorithm used to choose initial centers
Definition at line 717 of file hierarchical_clustering_index.h.
|
private |
Max size of leaf nodes
Definition at line 712 of file hierarchical_clustering_index.h.
|
private |
Memory occupied by the index.
Definition at line 691 of file hierarchical_clustering_index.h.
|
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.
|
private |
The root nodes in the tree.
Definition at line 677 of file hierarchical_clustering_index.h.
|
private |
How many parallel trees to build
Definition at line 702 of file hierarchical_clustering_index.h.