info.debatty.java.lsh

Class MinHash

java.lang.Object

info.debatty.java.lsh.MinHash

All Implemented Interfaces:

Serializable

public class MinHash
extends Object
implements Serializable

MinHash is a hashing scheme that tents to produce similar signatures for sets that have a high Jaccard similarity. The Jaccard similarity between two sets is the relative number of elements these sets have in common: J(A, B) = |A ∩ B| / |A ∪ B| A MinHash signature is a sequence of numbers produced by multiple hash functions hi. It can be shown that the Jaccard similarity between two sets is also the probability that this hash result is the same for the two sets: J(A, B) = Pr[hi(A) = hi(B)]. Therefore, MinHash signatures can be used to estimate Jaccard similarity between two sets. Moreover, it can be shown that the expected estimation error is O(1 / sqrt(n)), where n is the size of the signature (the number of hash functions that are used to produce the signature).

Author:

Thibault Debatty http://www.debatty.info

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
MinHash(double error, int dict_size) Initializes hash function to compute MinHash signatures for sets built from a dictionary of dict_size elements, with a given similarity estimation error.
MinHash(double error, int dict_size, long seed) Initializes hash function to compute MinHash signatures for sets built from a dictionary of dict_size elements, with a given similarity estimation error.
MinHash(int size, int dict_size) Initializes hash functions to compute MinHash signatures for sets built from a dictionary of dict_size elements.
MinHash(int size, int dict_size, long seed) Initializes hash functions to compute MinHash signatures for sets built from a dictionary of dict_size elements.

Method Summary

Methods

Modifier and Type	Method and Description
static Set<Integer>	convert2Set(boolean[] array) Convert a set represented as an array of booleans to a set of integer.
double	error() Computes the expected error of similarity computed using signatures.
long[][]	getCoefficients() Get the coefficients used by hash function hi.
static double	jaccardIndex(boolean[] s1, boolean[] s2) Compute the exact jaccard index between two sets, represented as arrays of booleans.
static double	jaccardIndex(Set<Integer> s1, Set<Integer> s2) Compute the jaccard index between two sets.
int[]	signature(boolean[] vector) Computes the signature for this set The input set is represented as an vector of booleans.
int[]	signature(Set<Integer> set) Computes the signature for this set.
double	similarity(int[] sig1, int[] sig2) Computes an estimation of Jaccard similarity (the number of elements in common) between two sets, using the MinHash signatures of these two sets.
static int	size(double error) Computes the size of the signature required to achieve a given error in similarity estimation.

Methods inherited from class java.lang.Object

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

Constructor Detail

MinHash

public MinHash(int size,
       int dict_size)

Initializes hash functions to compute MinHash signatures for sets built from a dictionary of dict_size elements.

Parameters:

size - the number of hash functions (and the size of resulting signatures)

dict_size -

MinHash

public MinHash(double error,
       int dict_size)

Initializes hash function to compute MinHash signatures for sets built from a dictionary of dict_size elements, with a given similarity estimation error.

Parameters:

error -

dict_size -

MinHash

public MinHash(int size,
       int dict_size,
       long seed)

Initializes hash functions to compute MinHash signatures for sets built from a dictionary of dict_size elements.

Parameters:

size - the number of hash functions (and the size of resulting signatures)

dict_size -

seed - random number generator seed. using the same value will guarantee identical hashes across object instantiations

MinHash

public MinHash(double error,
       int dict_size,
       long seed)

Initializes hash function to compute MinHash signatures for sets built from a dictionary of dict_size elements, with a given similarity estimation error.

Parameters:

error -

dict_size -

seed - random number generator seed. using the same value will guarantee identical hashes across object instantiations

Method Detail

jaccardIndex

public static double jaccardIndex(Set<Integer> s1,
                  Set<Integer> s2)

Compute the jaccard index between two sets.

Parameters:

s1 -

s2 -

Returns:

jaccardIndex

public static double jaccardIndex(boolean[] s1,
                  boolean[] s2)

Compute the exact jaccard index between two sets, represented as arrays of booleans.

Parameters:

s1 -

s2 -

Returns:

convert2Set

public static Set<Integer> convert2Set(boolean[] array)

Convert a set represented as an array of booleans to a set of integer.

Parameters:

array -

Returns:

size

public static int size(double error)

Computes the size of the signature required to achieve a given error in similarity estimation. (1 / error^2)

Parameters:

error -

Returns:

size of the signature

signature

public final int[] signature(boolean[] vector)

Computes the signature for this set The input set is represented as an vector of booleans. For example the array [true, false, true, true, false] corresponds to the set {0, 2, 3}

Parameters:

vector -

Returns:

the signature

signature

public final int[] signature(Set<Integer> set)

Computes the signature for this set. For example set = {0, 2, 3}

Parameters:

set -

Returns:

the signature

similarity

public final double similarity(int[] sig1,
                int[] sig2)

Computes an estimation of Jaccard similarity (the number of elements in common) between two sets, using the MinHash signatures of these two sets.

Parameters:

sig1 - MinHash signature of set1

sig2 - MinHash signature of set2 (produced using the same coefficients)

Returns:

the estimated similarity

error

public final double error()

Computes the expected error of similarity computed using signatures.

Returns:

the expected error

getCoefficients

public final long[][] getCoefficients()

Get the coefficients used by hash function hi.

Returns: