de.lmu.ifi.dbs.elki.index.lsh.hashfunctions

Class MultipleProjectionsLocalitySensitiveHashFunction

java.lang.Object

de.lmu.ifi.dbs.elki.index.lsh.hashfunctions.MultipleProjectionsLocalitySensitiveHashFunction

All Implemented Interfaces:

LocalitySensitiveHashFunction<NumberVector<?>>

@Reference(authors="M. Datar and N. Immorlica and P. Indyk and V. S. Mirrokni",
           title="Locality-sensitive hashing scheme based on p-stable distributions",
           booktitle="Proc. 20th annual symposium on Computational geometry",
           url="http://dx.doi.org/10.1145/997817.997857")
public class MultipleProjectionsLocalitySensitiveHashFunction
extends Object
implements LocalitySensitiveHashFunction<NumberVector<?>>

LSH hash function for vector space data. Depending on the choice of random vectors, it can be appropriate for Manhattan and Euclidean distances. Reference:

Locality-sensitive hashing scheme based on p-stable distributions
M. Datar and N. Immorlica and P. Indyk and V. S. Mirrokni
Proc. 20th annual symposium on Computational geometry

Field Summary

Fields

Modifier and Type	Field and Description
(package private) Matrix	projection Projection matrix.
(package private) int[]	randoms1 Random numbers for mixing the hash codes of the individual functions
(package private) double[]	shift Shift offset.
(package private) double	width Scaling factor.

Constructor Summary

Constructors

Constructor and Description
MultipleProjectionsLocalitySensitiveHashFunction(Matrix projection, double width, Random rnd) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
static int	fastModPrime(long data) Fast modulo operation for the largest unsigned integer prime.
int	hashObject(NumberVector<?> vec) Compute the hash value of an object

Methods inherited from class java.lang.Object

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

Field Detail

projection

Matrix projection

Projection matrix.

shift

double[] shift

Shift offset.

width

double width

Scaling factor.

randoms1

int[] randoms1

Random numbers for mixing the hash codes of the individual functions

Constructor Detail

MultipleProjectionsLocalitySensitiveHashFunction

public MultipleProjectionsLocalitySensitiveHashFunction(Matrix projection,
                                                double width,
                                                Random rnd)

Constructor.

Parameters:

projection - Projection vectors

width - Width of bins

rnd - Random number generator

Method Detail

hashObject

public int hashObject(NumberVector<?> vec)

Description copied from interface: LocalitySensitiveHashFunction

Compute the hash value of an object

Specified by:

hashObject in interface LocalitySensitiveHashFunction<NumberVector<?>>

Parameters:

vec - Object to hash

Returns:

Hash value

fastModPrime

public static int fastModPrime(long data)

Fast modulo operation for the largest unsigned integer prime.

Parameters:

data - Long input

Returns:

data % (2^32 - 5).