lshkit::StableDistLsh< DIST > Class Template Reference

Stable distribution based LSH. More...

#include <lsh.h>

List of all members.

Public Types

typedef const float * Domain

Public Member Functions

template<typename RNG>
void reset (const Parameter &param, RNG &rng)
template<typename RNG>
 StableDistLsh (const Parameter &param, RNG &rng)
unsigned getRange () const
unsigned operator() (Domain obj) const
unsigned operator() (Domain obj, float *delta) const
template<class Archive>
void serialize (Archive &ar, const unsigned int version)


struct  Parameter

Detailed Description

template<typename DIST>
class lshkit::StableDistLsh< DIST >

Stable distribution based LSH.

This LSH is defined on the D-dimensional vector space. For a vector X, the hash value is defined as

\[ h(X) = [b + a_1*X_1 + a_2*X_2 + ... + a_D*X_D] / W \]

where W is a positive value called the window size; b is sampled uniformly from [0, W); a1 ~ aD are N random variables independently sampled from the so-called stable distribution, which is specifiled by the template parameter DIST.

The domain of the LSH is (const float *), and the parameter is defined as

      struct Parameter {
          unsigned dim;
          float W;
The range of this LSH is 0.

Following are two spacial cases:

     typedef StableDistLsh<Cauchy> CauchyLsh;
     typedef StableDistLsh<Gaussian> GaussianLsh;
Cauchy distribution is 1-stable and Gaussian distribution is 2-stable. These two LSHes can be used to approximate L1 and L2 distances respectively.

For more information on stable distribution based LSH, see the following reference.

Mayur Datar , Nicole Immorlica , Piotr Indyk , Vahab S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA.

The documentation for this class was generated from the following file:
Get LSHKIT at Fast, secure and Free Open Source software downloads doxygen