lshkit::ThresholdingLsh Class Reference

Random hyperplane based LSH for L1 distance. 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>
 ThresholdingLsh (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

Random hyperplane based LSH for L1 distance.

This LSH can be used to approximate L1 distance for closed D-dimensional space [min, max]^D. It hashes each input vector into a 0-1 value, so its range is 2. The hash function is the following: a random dimension is chosen, and a threshold T is sampled uniformly in [min, max]. For each input vector, the value at that dimension is check. If the value is larger than T, 1 is returned and otherwise 0 is returned. Following is the parameter.

   struct Parameter
       unsigned dim;  // Dimension of domain.
       float min;     // Each dimension is limited in [min, max].
       float max;

The method is discussed in the following papers:

Zhe Wang, Wei Dong, William Josephson, Qin Lv, Moses Charikar, Kai Li. Sizing Sketches: A Rank-Based Analysis for Similarity Search. In Proceedings of the 2007 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems . San Diego, CA, USA. June 2007.

Qin Lv, Moses Charikar, Kai Li. Image Similarity Search with Compact Data Structures. In Proceedings of ACM 13th Conference on Information and Knowledge Management (CIKM), Washington D.C., USA. November 2004.

Note that the original method allows the range of each dimension to be different and also allow each dimensioin to carry a weight. The implementation here is simplified.

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