info.debatty.java.lsh

Class SuperBit

java.lang.Object

info.debatty.java.lsh.SuperBit

All Implemented Interfaces:

Serializable

public class SuperBit
extends Object
implements Serializable

Implementation of Super-Bit Locality-Sensitive Hashing. Super-Bit is an improvement of Random Projection LSH. It computes an estimation of cosine similarity. Super-Bit Locality-Sensitive Hashing Jianqiu Ji, Jianmin Li, Shuicheng Yan, Bo Zhang, Qi Tian http://papers.nips.cc/paper/4847-super-bit-locality-sensitive-hashing.pdf Advances in Neural Information Processing Systems 25, 2012 Supported input types: - SparseIntegerVector - double[] - others to come...

Author:

Thibault Debatty

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
SuperBit() Initialize SuperBit algorithm without parameters (used only for serialization).
SuperBit(int d) Initialize SuperBit algorithm.
SuperBit(int d, int n, int l) Initialize SuperBit algorithm.
SuperBit(int d, int n, int l, long seed) Initialize SuperBit algorithm.

Method Summary

Methods

Modifier and Type	Method and Description
static double	cosineSimilarity(double[] v1, double[] v2) Computes the cosine similarity, computed as v1 dot v2 / (|v1| * |v2|).
double[][]	getHyperplanes() Get the hyperplanes coefficients used to compute signatures.
boolean[]	signature(double[] vector) Compute the signature of this vector.
boolean[]	signature(info.debatty.java.utils.SparseDoubleVector vector) Compute the signature of this vector.
boolean[]	signature(info.debatty.java.utils.SparseIntegerVector vector) Compute the signature of this vector.
double	similarity(boolean[] sig1, boolean[] sig2) Compute the similarity between two signature, which is also an estimation of the cosine similarity between the two vectors.

Methods inherited from class java.lang.Object

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

Constructor Detail

SuperBit

public SuperBit(int d,
        int n,
        int l)

Initialize SuperBit algorithm. Super-Bit depth n must be [1 .. d] and number of Super-Bit l in [1 .. The resulting code length k = n * l The K vectors are orthogonalized in L batches of N vectors

Parameters:

d - data space dimension

n - Super-Bit depth [1 .. d]

l - number of Super-Bit [1 ..

SuperBit

public SuperBit(int d,
        int n,
        int l,
        long seed)

Initialize SuperBit algorithm. Super-Bit depth n must be [1 .. d] and number of Super-Bit l in [1 .. The resulting code length k = n * l The K vectors are orthogonalized in L batches of N vectors

Parameters:

d - data space dimension

n - Super-Bit depth [1 .. d]

l - number of Super-Bit [1 ..

seed - to use for the random number generator

SuperBit

public SuperBit(int d)

Initialize SuperBit algorithm. With code length K = 10000 The K vectors are orthogonalized in d batches of 10000/d vectors The resulting mean error is 0.01

Parameters:

d -

SuperBit

public SuperBit()

Initialize SuperBit algorithm without parameters (used only for serialization).

Method Detail

signature

public final boolean[] signature(info.debatty.java.utils.SparseIntegerVector vector)

Compute the signature of this vector.

Parameters:

vector -

Returns:

signature

public final boolean[] signature(info.debatty.java.utils.SparseDoubleVector vector)

Compute the signature of this vector.

Parameters:

vector -

Returns:

signature

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

Compute the signature of this vector.

Parameters:

vector -

Returns:

similarity

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

Compute the similarity between two signature, which is also an estimation of the cosine similarity between the two vectors.

Parameters:

sig1 -

sig2 -

Returns:

estimated cosine similarity

getHyperplanes

public final double[][] getHyperplanes()

Get the hyperplanes coefficients used to compute signatures.

Returns:

cosineSimilarity

public static double cosineSimilarity(double[] v1,
                      double[] v2)

Computes the cosine similarity, computed as v1 dot v2 / (|v1| * |v2|). Cosine similarity of two vectors is the cosine of the angle between them. It ranges between -1 and +1

Parameters:

v1 -

v2 -

Returns: