rtflann::LshIndex< Distance > Class Template Reference

#include <lsh_index.h>

Inheritance diagram for rtflann::LshIndex< Distance >:

Classes
struct	SortScoreIndexPairOnSecond

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 &) const
flann_algorithm_t	getType () const
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< size_t > > &indices, std::vector< std::vector< DistanceType > > &dists, size_t knn, const SearchParams &params) const
	Perform k-nearest neighbor search. More...
void	loadIndex (FILE *stream)
	LshIndex (const IndexParams &params=LshIndexParams(), Distance d=Distance())
	LshIndex (const Matrix< ElementType > &input_data, const IndexParams &params=LshIndexParams(), Distance d=Distance())
	LshIndex (const LshIndex &other)
LshIndex &	operator= (LshIndex other)
void	saveIndex (FILE *stream)
template<typename Archive >
void	serialize (Archive &ar)
int	usedMemory () const
virtual	~LshIndex ()
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)
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 ()
void	freeIndex ()
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 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
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::LshIndex< Distance >

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 78 of file lsh_index.h.

Member Typedef Documentation

BaseClass

template<typename Distance >

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

Definition at line 84 of file lsh_index.h.

DistanceType

template<typename Distance >

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

Definition at line 82 of file lsh_index.h.

ElementType

template<typename Distance >

typedef Distance::ElementType rtflann::LshIndex< Distance >::ElementType

Definition at line 81 of file lsh_index.h.

ScoreIndexPair

template<typename Distance >

typedef std::pair<float, unsigned int> rtflann::LshIndex< Distance >::ScoreIndexPair

private

Defines the comparator on score and index

Definition at line 377 of file lsh_index.h.

Constructor & Destructor Documentation

LshIndex() [1/3]

template<typename Distance >

rtflann::LshIndex< Distance >::LshIndex ( const IndexParams &  params = LshIndexParams(), Distance  d = Distance()  )

inline

Constructor

Parameters

params	parameters passed to the LSH algorithm
d	the distance used

Definition at line 90 of file lsh_index.h.

LshIndex() [2/3]

template<typename Distance >

rtflann::LshIndex< Distance >::LshIndex ( const Matrix< ElementType > &  input_data, const IndexParams &  params = LshIndexParams(), Distance  d = Distance()  )

inline

Constructor

Parameters

input_data	dataset with the input features
params	parameters passed to the LSH algorithm
d	the distance used

Definition at line 106 of file lsh_index.h.

LshIndex() [3/3]

template<typename Distance >

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

inline

Definition at line 118 of file lsh_index.h.

~LshIndex()

template<typename Distance >

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

inlinevirtual

Definition at line 133 of file lsh_index.h.

Member Function Documentation

addPoints()

template<typename Distance >

void rtflann::LshIndex< 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 146 of file lsh_index.h.

buildIndexImpl()

template<typename Distance >

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

inlineprotectedvirtual

Builds the index

Implements rtflann::NNIndex< Distance >.

Definition at line 351 of file lsh_index.h.

clone()

template<typename Distance >

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

inlinevirtual

Implements rtflann::NNIndex< Distance >.

Definition at line 139 of file lsh_index.h.

fill_xor_mask()

template<typename Distance >

void rtflann::LshIndex< Distance >::fill_xor_mask ( lsh::BucketKey  key, int  lowest_index, unsigned int  level, std::vector< lsh::BucketKey > &  xor_masks  )

inlineprivate

Fills the different xor masks to use when getting the neighbors in multi-probe LSH

Parameters

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 392 of file lsh_index.h.

findNeighbors()

template<typename Distance >

void rtflann::LshIndex< Distance >::findNeighbors ( ResultSet< DistanceType > &  result, const ElementType *  vec, const 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 maxCheck = the maximum number of restarts (in a best-bin-first manner)

Implements rtflann::NNIndex< Distance >.

Definition at line 341 of file lsh_index.h.

freeIndex()

template<typename Distance >

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

inlineprotectedvirtual

Implements rtflann::NNIndex< Distance >.

Definition at line 368 of file lsh_index.h.

getNeighbors() [1/2]

template<typename Distance >

void rtflann::LshIndex< Distance >::getNeighbors ( const ElementType *  vec, bool  do_radius, float  radius, bool  do_k, unsigned int  k_nn, float &  checked_average  )

inlineprivate

Performs the approximate nearest-neighbor search.

Parameters

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 412 of file lsh_index.h.

getNeighbors() [2/2]

template<typename Distance >

void rtflann::LshIndex< Distance >::getNeighbors ( const ElementType *  vec, ResultSet< DistanceType > &  result  ) const

inlineprivate

Performs the approximate nearest-neighbor search. This is a slower version than the above as it uses the ResultSet

Parameters

vec	the feature to analyze

Definition at line 490 of file lsh_index.h.

getType()

template<typename Distance >

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

inlinevirtual

Implements rtflann::IndexBase.

Definition at line 167 of file lsh_index.h.

knnSearch() [1/2]

template<typename Distance >

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

inlinevirtual

Perform k-nearest neighbor search.

Parameters

[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 224 of file lsh_index.h.

knnSearch() [2/2]

template<typename Distance >

int rtflann::LshIndex< Distance >::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

inlinevirtual

Perform k-nearest neighbor search.

Parameters

[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 279 of file lsh_index.h.

loadIndex()

template<typename Distance >

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

inlinevirtual

Implements rtflann::IndexBase.

Definition at line 201 of file lsh_index.h.

operator=()

template<typename Distance >

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

inline

Definition at line 127 of file lsh_index.h.

saveIndex()

template<typename Distance >

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

inlinevirtual

Implements rtflann::IndexBase.

Definition at line 195 of file lsh_index.h.

serialize()

template<typename Distance >

template<typename Archive >

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

inline

Definition at line 174 of file lsh_index.h.

swap()

template<typename Distance >

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

inlineprivate

Definition at line 520 of file lsh_index.h.

usedMemory()

template<typename Distance >

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

inlinevirtual

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

Implements rtflann::IndexBase.

Definition at line 211 of file lsh_index.h.

Member Data Documentation

key_size_

template<typename Distance >

unsigned int rtflann::LshIndex< Distance >::key_size_

private

key size

Definition at line 537 of file lsh_index.h.

multi_probe_level_

template<typename Distance >

unsigned int rtflann::LshIndex< Distance >::multi_probe_level_

private

How far should we look for neighbors in multi-probe LSH

Definition at line 539 of file lsh_index.h.

table_number_

template<typename Distance >

unsigned int rtflann::LshIndex< Distance >::table_number_

private

table number

Definition at line 535 of file lsh_index.h.

tables_

template<typename Distance >

std::vector<lsh::LshTable<ElementType> > rtflann::LshIndex< Distance >::tables_

private

The different hash tables

Definition at line 532 of file lsh_index.h.

xor_masks_

template<typename Distance >

std::vector<lsh::BucketKey> rtflann::LshIndex< Distance >::xor_masks_

private

The XOR masks to apply to a key to get the neighboring buckets

Definition at line 542 of file lsh_index.h.

---

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

• lsh_index.h