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:

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

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field and Description
(package private) double	iwidth Scaling factor: inverse of width.
private static long	MASK32 Bit mask for signed int to unsigned long conversion.
(package private) RandomProjectionFamily.Projection	projection Projection matrix.
(package private) int[]	randoms1 Random numbers for mixing the hash codes of the individual functions
(package private) double[]	shift Shift offset.

Constructor Summary

Constructors

Constructor and Description
MultipleProjectionsLocalitySensitiveHashFunction(RandomProjectionFamily.Projection 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	getNumberOfProjections() Get the number of projections performed.
int	hashObject(NumberVector vec) Compute the hash value of an object.
int	hashObject(NumberVector vec, double[] buf) Compute the hash value of an object (faster version).

Methods inherited from class java.lang.Object

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

Field Detail

projection

RandomProjectionFamily.Projection projection

Projection matrix.

shift

double[] shift

Shift offset.

iwidth

double iwidth

Scaling factor: inverse of width.

randoms1

int[] randoms1

Random numbers for mixing the hash codes of the individual functions

MASK32

private static final long MASK32

Bit mask for signed int to unsigned long conversion.

See Also:

Constant Field Values

Constructor Detail

MultipleProjectionsLocalitySensitiveHashFunction

public MultipleProjectionsLocalitySensitiveHashFunction(RandomProjectionFamily.Projection 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

hashObject

public int hashObject(NumberVector vec,
             double[] buf)

Description copied from interface: LocalitySensitiveHashFunction

Compute the hash value of an object (faster version).

Specified by:

hashObject in interface LocalitySensitiveHashFunction<NumberVector>

Parameters:

vec - Object to hash

buf - Buffer, sized according to the number of projections.

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).

getNumberOfProjections

public int getNumberOfProjections()

Description copied from interface: LocalitySensitiveHashFunction

Get the number of projections performed.

Specified by:

getNumberOfProjections in interface LocalitySensitiveHashFunction<NumberVector>

Returns:

Number of projections.