datafu.pig.hash.lsh.p_stable

Class AbstractStableDistributionFunction

java.lang.Object

datafu.pig.hash.lsh.interfaces.LSH

datafu.pig.hash.lsh.p_stable.AbstractStableDistributionFunction

Direct Known Subclasses:

L1LSH, L2LSH

public abstract class AbstractStableDistributionFunction
extends LSH

This is the base-class for all p-stable based locality sensitive hashes. p-stable locality sensitive hashes are defined by a few parameters: a dimension, d , a vector taken from a k-stable distribution (where k is 1 or 2) and a width of projection, w.

All p-stable LSH functions are parameterized with a quantization parameter (w or r in the literature , depending on where you look). Consider the following excerpt from Datar, M.; Immorlica, N.; Indyk, P.; Mirrokni, V.S. (2004). "Locality-Sensitive Hashing Scheme Based on p-Stable Distributions". Proceedings of the Symposium on Computational Geometry.

Decreasing the width of the projection (w) decreases the probability of collision for any two points. Thus, it has the same effect as increasing k . As a result, we would like to set w as small as possible and in this way decrease the number of projections we need to make.

In the literature, the quantization parameter (or width of the projection) is found empirically given a sample of the data and the likely threshold for the metric. Tuning this parameter is very important for the performance of this algorithm. For more information, see Datar, M.; Immorlica, N.; Indyk, P.; Mirrokni, V.S. (2004). "Locality-Sensitive Hashing Scheme Based on p-Stable Distributions". Proceedings of the Symposium on Computational Geometry.

Field Summary

Fields inherited from class datafu.pig.hash.lsh.interfaces.LSH

dim, rg

Constructor Summary

Constructors

Constructor and Description
AbstractStableDistributionFunction(int dim, double w, org.apache.commons.math.random.RandomGenerator rand) Constructs a new instance.

Method Summary

Modifier and Type	Method and Description
long	apply(org.apache.commons.math.linear.RealVector vector) Compute the LSH for a given vector.
protected abstract Sampler	getSampler() The sampler determines the metric which this LSH is associated with.
void	reset(int dim, double w)

Methods inherited from class datafu.pig.hash.lsh.interfaces.LSH

getDim, getRandomGenerator

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AbstractStableDistributionFunction

public AbstractStableDistributionFunction(int dim,
                                          double w,
                                          org.apache.commons.math.random.RandomGenerator rand)
                                   throws org.apache.commons.math.MathException

Constructs a new instance.

Parameters:

dim - The dimension of the vectors to be hashed

w - A double representing the quantization parameter (also known as the projection width)

rand - The random generator used

Throws:

org.apache.commons.math.MathException - MathException

Method Detail

reset

public void reset(int dim,
                  double w)
           throws org.apache.commons.math.MathException

Throws:

org.apache.commons.math.MathException

getSampler

protected abstract Sampler getSampler()

The sampler determines the metric which this LSH is associated with. A 1-stable sample will yield a LSH which corresponds to a L1 metric; likewise for 2-stable and L2.

Returns:

The sampler to use.

apply

public long apply(org.apache.commons.math.linear.RealVector vector)

Compute the LSH for a given vector.

Specified by:

apply in class LSH

Parameters:

vector - A vector to be hashed

Returns:

A hash which collides with vectors close according to some metric (implementation dependent).