jsat.linear.vectorcollection.lsh

Class RandomProjectionLSH<V extends Vec>

java.lang.Object

jsat.linear.vectorcollection.lsh.RandomProjectionLSH<V>

All Implemented Interfaces:

Serializable, Cloneable, VectorCollection<V>

public class RandomProjectionLSH<V extends Vec>
extends Object
implements VectorCollection<V>

An implementation of Locality Sensitive Hashing for the CosineDistance using random projections. This forms a vector collection that performs a linear search of the data set, but does so in a more efficient manner by comparing hamming distances in a byte array. However, the reported distances are only approximations - and may not be correct. For this reason the results are also approximate.

See:

• Charikar, M. S. (2002). Similarity estimation techniques from rounding algorithms. Proceedings of the thiry-fourth annual ACM symposium on Theory of computing - STOC ’02 (pp. 380–388). New York, New York, USA: ACM Press. doi:10.1145/509907.509965
• Durme, B. Van,&Lall, A. (2010). Online Generation of Locality Sensitive Hash Signatures. Proceedings of the ACL 2010 Conference Short Papers (pp. 231–235). Stroudsburg, PA, USA.

Author:

Edward Raff

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	RandomProjectionLSH.RandomProjectionLSHFactory<V extends Vec>

Constructor Summary

Constructors

Modifier	Constructor and Description
	RandomProjectionLSH(List<V> vecs, int ints, boolean inMemory) Creates a new Random Projection LSH object that uses a full matrix of normally distributed values.
	RandomProjectionLSH(List<V> vecs, int ints, int poolSize) Creates a new Random Projection LSH object that uses a pool of normally distributed values to approximate a full matrix with considerably less memory storage.
protected	RandomProjectionLSH(RandomProjectionLSH<V> toCopy) Copy Constructor

Method Summary

Modifier and Type	Method and Description
VectorCollection<V>	clone()
int	getSignatureBitLength() Returns the signature or encoding length in bits.
List<? extends VecPaired<V,Double>>	search(Vec query, double range) Searches the space for all vectors that are within a given range of the query vector.
List<? extends VecPaired<V,Double>>	search(Vec query, int neighbors) Searches the space for the k neighbors that are closest to the given query vector
int	size() Returns the number of vectors stored in the collection

Methods inherited from class java.lang.Object

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

Constructor Detail

RandomProjectionLSH

public RandomProjectionLSH(List<V> vecs,
                           int ints,
                           boolean inMemory)

Creates a new Random Projection LSH object that uses a full matrix of normally distributed values.

Parameters:

vecs - the list of vectors to form a collection for

ints - the number of integers to use for the encoding

inMemory - true to construct the full matrix in memory, or false to construct the needed values on demand. This reduces memory use at increased CPU usage.

RandomProjectionLSH

public RandomProjectionLSH(List<V> vecs,
                           int ints,
                           int poolSize)

Creates a new Random Projection LSH object that uses a pool of normally distributed values to approximate a full matrix with considerably less memory storage.

Parameters:

vecs - the list of vectors to form a collection for

ints - the number of integers to use for the encoding

poolSize - the number of normally distributed random variables to store. Matrix values will be pulled on demand from an index in the pool of values.

RandomProjectionLSH

protected RandomProjectionLSH(RandomProjectionLSH<V> toCopy)

Copy Constructor

Parameters:

toCopy - the object to copy

Method Detail

search

public List<? extends VecPaired<V,Double>> search(Vec query,
                                                  double range)

Description copied from interface: VectorCollection

Searches the space for all vectors that are within a given range of the query vector.

Specified by:

search in interface VectorCollection<V extends Vec>

Parameters:

query - the vector we want to find others near

range - the search range around our query

Returns:

the list of all vectors within the range of our query. The paired value contains the distance to the query vector.

search

public List<? extends VecPaired<V,Double>> search(Vec query,
                                                  int neighbors)

Description copied from interface: VectorCollection

Searches the space for the k neighbors that are closest to the given query vector

Specified by:

search in interface VectorCollection<V extends Vec>

Parameters:

query - the vector we want to find neighbors of

neighbors - the maximum number of neighbors to return

Returns:

the list the k nearest neighbors, in sorted order from closest to farthest. The paired value contains the distance to the query vector

getSignatureBitLength

public int getSignatureBitLength()

Returns the signature or encoding length in bits.

Returns:

the signature length in bits

size

public int size()

Description copied from interface: VectorCollection

Returns the number of vectors stored in the collection

Specified by:

size in interface VectorCollection<V extends Vec>

Returns:

the size of the collection

clone

public VectorCollection<V> clone()

Specified by:

clone in interface VectorCollection<V extends Vec>

Overrides:

clone in class Object