#include <lsh_index.h>
Classes | |
struct | SortScoreIndexPairOnSecond |
Public Types | |
typedef NNIndex< Distance > | BaseClass |
typedef Distance::ResultType | DistanceType |
typedef Distance::ElementType | ElementType |
![]() | |
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 &) const |
flann_algorithm_t | getType () const |
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< size_t > > &indices, std::vector< std::vector< DistanceType > > &dists, size_t knn, const SearchParams ¶ms) const |
Perform k-nearest neighbor search. More... | |
void | loadIndex (FILE *stream) |
LshIndex (const IndexParams ¶ms=LshIndexParams(), Distance d=Distance()) | |
LshIndex (const LshIndex &other) | |
LshIndex (const Matrix< ElementType > &input_data, const IndexParams ¶ms=LshIndexParams(), Distance d=Distance()) | |
LshIndex & | operator= (LshIndex other) |
void | saveIndex (FILE *stream) |
template<typename Archive > | |
void | serialize (Archive &ar) |
int | usedMemory () const |
virtual | ~LshIndex () |
![]() | |
virtual void | buildIndex () |
virtual void | buildIndex (const Matrix< ElementType > &dataset) |
IndexParams | getParameters () const |
virtual ElementType * | getPoint (size_t id) |
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 |
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 | freeIndex () |
![]() | |
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 std::pair< float, unsigned int > | ScoreIndexPair |
Private Member Functions | |
void | fill_xor_mask (lsh::BucketKey key, int lowest_index, unsigned int level, std::vector< lsh::BucketKey > &xor_masks) |
void | getNeighbors (const ElementType *vec, bool do_radius, float radius, bool do_k, unsigned int k_nn, float &checked_average) |
void | getNeighbors (const ElementType *vec, ResultSet< DistanceType > &result) const |
void | swap (LshIndex &other) |
Private Attributes | |
unsigned int | key_size_ |
unsigned int | multi_probe_level_ |
unsigned int | table_number_ |
std::vector< lsh::LshTable< ElementType > > | tables_ |
std::vector< lsh::BucketKey > | xor_masks_ |
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_ |
Randomized kd-tree index
Contains the k-d trees and other information for indexing a set of points for nearest-neighbor matching.
Definition at line 108 of file lsh_index.h.
typedef NNIndex<Distance> rtflann::LshIndex< Distance >::BaseClass |
Definition at line 114 of file lsh_index.h.
typedef Distance::ResultType rtflann::LshIndex< Distance >::DistanceType |
Definition at line 112 of file lsh_index.h.
typedef Distance::ElementType rtflann::LshIndex< Distance >::ElementType |
Definition at line 111 of file lsh_index.h.
|
private |
Defines the comparator on score and index
Definition at line 407 of file lsh_index.h.
|
inline |
Constructor
params | parameters passed to the LSH algorithm |
d | the distance used |
Definition at line 120 of file lsh_index.h.
|
inline |
Constructor
input_data | dataset with the input features |
params | parameters passed to the LSH algorithm |
d | the distance used |
Definition at line 136 of file lsh_index.h.
|
inline |
Definition at line 148 of file lsh_index.h.
|
inlinevirtual |
Definition at line 163 of file lsh_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 176 of file lsh_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 381 of file lsh_index.h.
|
inlinevirtual |
Implements rtflann::NNIndex< Distance >.
Definition at line 169 of file lsh_index.h.
|
inlineprivate |
Fills the different xor masks to use when getting the neighbors in multi-probe LSH
key | the key we build neighbors from |
lowest_index | the lowest index of the bit set |
level | the multi-probe level we are at |
xor_masks | all the xor mask |
Definition at line 422 of file lsh_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 maxCheck = the maximum number of restarts (in a best-bin-first manner)
Implements rtflann::NNIndex< Distance >.
Definition at line 371 of file lsh_index.h.
|
inlineprotectedvirtual |
Implements rtflann::NNIndex< Distance >.
Definition at line 398 of file lsh_index.h.
|
inlineprivate |
Performs the approximate nearest-neighbor search.
vec | the feature to analyze |
do_radius | flag indicating if we check the radius too |
radius | the radius if it is a radius search |
do_k | flag indicating if we limit the number of nn |
k_nn | the number of nearest neighbors |
checked_average | used for debugging |
Definition at line 442 of file lsh_index.h.
|
inlineprivate |
Performs the approximate nearest-neighbor search. This is a slower version than the above as it uses the ResultSet
vec | the feature to analyze |
Definition at line 520 of file lsh_index.h.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 197 of file lsh_index.h.
|
inlinevirtual |
Perform k-nearest neighbor search.
[in] | queries | The query points for which to find the nearest neighbors |
[out] | indices | The indices of the nearest neighbors found |
[out] | dists | Distances to the nearest neighbors found |
[in] | knn | Number of nearest neighbors to return |
[in] | params | Search parameters |
Reimplemented from rtflann::NNIndex< Distance >.
Definition at line 254 of file lsh_index.h.
|
inlinevirtual |
Perform k-nearest neighbor search.
[in] | queries | The query points for which to find the nearest neighbors |
[out] | indices | The indices of the nearest neighbors found |
[out] | dists | Distances to the nearest neighbors found |
[in] | knn | Number of nearest neighbors to return |
[in] | params | Search parameters |
Reimplemented from rtflann::NNIndex< Distance >.
Definition at line 309 of file lsh_index.h.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 231 of file lsh_index.h.
|
inline |
Definition at line 157 of file lsh_index.h.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 225 of file lsh_index.h.
|
inline |
Definition at line 204 of file lsh_index.h.
|
inlineprivate |
Definition at line 550 of file lsh_index.h.
|
inlinevirtual |
Computes the index memory usage Returns: memory used by the index
Implements rtflann::IndexBase.
Definition at line 241 of file lsh_index.h.
|
private |
key size
Definition at line 567 of file lsh_index.h.
|
private |
How far should we look for neighbors in multi-probe LSH
Definition at line 569 of file lsh_index.h.
|
private |
table number
Definition at line 565 of file lsh_index.h.
|
private |
The different hash tables
Definition at line 562 of file lsh_index.h.
|
private |
The XOR masks to apply to a key to get the neighboring buckets
Definition at line 572 of file lsh_index.h.