datafu.pig.hash.lsh.interfaces

Class LSH

java.lang.Object

datafu.pig.hash.lsh.interfaces.LSH

Direct Known Subclasses:

AbstractStableDistributionFunction, HyperplaneLSH, RepeatingLSH

public abstract class LSH
extends java.lang.Object

An abstract class representing a locality sensitive hash. From wikipedia's article on Locality Sensitive Hashing:

Locality-sensitive hashing (LSH) is a method of performing probabilistic dimension reduction of high-dimensional data. The basic idea is to hash the input items so that similar items are mapped to the same buckets with high probability (the number of buckets being much smaller than the universe of possible input items).

Field Summary

Fields

Modifier and Type	Field and Description
protected int	dim
protected org.apache.commons.math.random.RandomGenerator	rg

Constructor Summary

Constructors

Constructor and Description
LSH(int dim, org.apache.commons.math.random.RandomGenerator rg) Construct a locality sensitive hash.

Method Summary

Modifier and Type	Method and Description
abstract long	apply(org.apache.commons.math.linear.RealVector vector) Hash a vector.
int	getDim()
org.apache.commons.math.random.RandomGenerator	getRandomGenerator()

Methods inherited from class java.lang.Object

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

Field Detail

rg

protected org.apache.commons.math.random.RandomGenerator rg

dim

protected int dim

Constructor Detail

LSH

public LSH(int dim,
           org.apache.commons.math.random.RandomGenerator rg)

Construct a locality sensitive hash. Note, one may pass a pre-seeded generator.

Parameters:

dim - The dimension of the vectors which are to be hashed

rg - The random generator to use internally.

Method Detail

getRandomGenerator

public org.apache.commons.math.random.RandomGenerator getRandomGenerator()

Returns:

The random generator from this LSH

getDim

public int getDim()

Returns:

The dimension of the vectors which this LSh supports

apply

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

Hash a vector.

Parameters:

vector - A vector to be hashed

Returns:

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