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

Class CosineHashFunctionFamily

java.lang.Object

de.lmu.ifi.dbs.elki.index.lsh.hashfamilies.CosineHashFunctionFamily

All Implemented Interfaces:

LocalitySensitiveHashFunctionFamily<NumberVector>

@Reference(authors="M.S. Charikar",
           title="Similarity estimation techniques from rounding algorithms",
           booktitle="Proc. 34th ACM Symposium on Theory of computing, STOC\'02",
           url="https://dx.doi.org/10.1145/509907.509965")
public class CosineHashFunctionFamily
extends Object
implements LocalitySensitiveHashFunctionFamily<NumberVector>

Hash function family to use with Cosine distance, using simplified hash functions where the projection is only drawn from +-1, instead of Gaussian distributions. References:

M.S. Charikar
Similarity estimation techniques from rounding algorithms
Proc. 34th ACM Symposium on Theory of computing, STOC'02

M. Henzinger
Finding near-duplicate web pages: a large-scale evaluation of algorithms
Proc. 29th ACM Conference on Research and Development in Information Retrieval. ACM SIGIR, 2006

Author:

Evgeniy Faerman

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	CosineHashFunctionFamily.Parameterizer Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
private int	k The number of projections to use for each hash function.
private RandomProjectionFamily	proj Projection family to use.

Constructor Summary

Constructors

Constructor and Description
CosineHashFunctionFamily(int k, RandomFactory random) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
ArrayList<? extends LocalitySensitiveHashFunction<? super NumberVector>>	generateHashFunctions(Relation<? extends NumberVector> relation, int l) Generate hash functions for the given relation.
TypeInformation	getInputTypeRestriction() Get the input type information.
boolean	isCompatible(DistanceFunction<?> df) Check whether the given distance function can be accelerated using this hash family.

Methods inherited from class java.lang.Object

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

Field Detail

proj

private RandomProjectionFamily proj

Projection family to use.

k

private int k

The number of projections to use for each hash function.

Constructor Detail

CosineHashFunctionFamily

public CosineHashFunctionFamily(int k,
                        RandomFactory random)

Constructor.

Parameters:

k - Number of projections to use.

random - Random factory.

Method Detail

getInputTypeRestriction

public TypeInformation getInputTypeRestriction()

Description copied from interface: LocalitySensitiveHashFunctionFamily

Get the input type information.

Specified by:

getInputTypeRestriction in interface LocalitySensitiveHashFunctionFamily<NumberVector>

Returns:

Input type information.

generateHashFunctions

public ArrayList<? extends LocalitySensitiveHashFunction<? super NumberVector>> generateHashFunctions(Relation<? extends NumberVector> relation,
                                                                                             int l)

Description copied from interface: LocalitySensitiveHashFunctionFamily

Generate hash functions for the given relation.

Specified by:

generateHashFunctions in interface LocalitySensitiveHashFunctionFamily<NumberVector>

Parameters:

relation - Relation to index

l - Number of hash tables to use

Returns:

Family of hash functions

isCompatible

public boolean isCompatible(DistanceFunction<?> df)

Description copied from interface: LocalitySensitiveHashFunctionFamily

Check whether the given distance function can be accelerated using this hash family.

Specified by:

isCompatible in interface LocalitySensitiveHashFunctionFamily<NumberVector>

Parameters:

df - Distance function.

Returns:

true when appropriate.