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)
Classes
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

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:

• include/lshkit/lsh.h

---