jsat.linear.vectorcollection.lsh

Class E2LSH<V extends Vec>

java.lang.Object

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

public class E2LSH<V extends Vec>
extends Object

This is an implementation of Locality Sensitive Hashing for the L1 and L2 distance metrics. This is essentially a vector collection that can only perform a radius search for a pre-defined radius. In addition, the results are only approximate - not all of the correct points may be returned, and it is possible no points will be returned when the truth is that some data points do exist.

Searching is done using the searchR(jsat.linear.Vec, boolean) methods. While the set of points returned is approximate, the distance values are exact. This is because no approximate distance is available, so the distances must be computed to remove violators.

LSH may be useful if any of the following apply to your problem

• Only need to do a radius searches of a small number of fixed size increments
• You need only the first few nearest neighbors, and can compute a threshold for the NN
• Approximate neighbor results do not heavily impact the results of your algorithm
• You want to find near-duplicates in a data set

This implementation is based heavily on the following, but is not an exact re-implementation.

See:

• Datar, M., Immorlica, N., Indyk, P.,&Mirrokni, V. S. (2004). Locality-sensitive hashing scheme based on p-stable distributions. Proceedings of the twentieth annual symposium on Computational geometry - SCG ’04 (pp. 253–262). New York, New York, USA: ACM Press. doi:10.1145/997817.997857
• Andoni, Alex (2005). E2LSH Manual 0.1

Author:

Edward Raff

Constructor Summary

Constructors

Constructor and Description
E2LSH(List<V> vecs, double radius, double eps, int w, int k, double delta, DistanceMetric dm) Creates a new LSH scheme for a given distance metric
E2LSH(List<V> vecs, double radius, double eps, int w, int k, double delta, DistanceMetric dm, List<Double> distCache) Creates a new LSH scheme for a given distance metric

Method Summary

Modifier and Type	Method and Description
double	getC() Returns the multiplier used on the radius that controls the degree of approximation.
int	getL() Returns how many separate hash tables have been created for this distance metric.
double	getRadius() Returns the desired approximate radius for which to return results
List<? extends VecPaired<Vec,Double>>	searchR(Vec q) Performs a search for points within the set radius of the query point.
List<? extends VecPaired<Vec,Double>>	searchR(Vec q, boolean approx) Performs a search for points within the set radius of the query point.

Methods inherited from class java.lang.Object

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

Constructor Detail

E2LSH

public E2LSH(List<V> vecs,
             double radius,
             double eps,
             int w,
             int k,
             double delta,
             DistanceMetric dm,
             List<Double> distCache)

Creates a new LSH scheme for a given distance metric

Parameters:

vecs - the set of vector to place into the LSH

radius - the searchR radius for vectors

eps - the approximation error, where vectors as fast as R(1+eps) are likely to be returned. Must be positive.

w - the projection radius. If given a value <= 0, a default value of 4 will be used.

k - the number of hash functions to conjoin into the final hash per vector. If a value <= 0 is given, a default value will be computed.

delta - (1-delta) will be the desired minimum probability of correctly selecting the correct nearest neighbor if there is only 1-NN within a distance of radius. It will be used to determine some number getL() hash tables to reach the desired probability. 0.10 is a good value.

dm - the distance metric to use, must be EuclideanDistance or ManhattanDistance.

distCache - the distance acceleration cache to use, if null, and it is supported, one will not be built. This is provided to a void redundant calculation when initializing multiple LSH tables using the same data set.

E2LSH

public E2LSH(List<V> vecs,
             double radius,
             double eps,
             int w,
             int k,
             double delta,
             DistanceMetric dm)

Creates a new LSH scheme for a given distance metric

Parameters:

vecs - the set of vector to place into the LSH

radius - the searchR radius for vectors

eps - the approximation error, where vectors as fast as R(1+eps) are likely to be returned. Must be positive.

w - the projection radius. If given a value <= 0, a default value of 4 will be used.

k - the number of hash functions to conjoin into the final hash per vector. If a value <= 0 is given, a default value will be computed.

delta - (1-delta) will be the desired minimum probability of correctly selecting the correct nearest neighbor if there is only 1-NN within a distance of radius. It will be used to determine some number getL() hash tables to reach the desired probability. 0.10 is a good value.

dm - the distance metric to use, must be EuclideanDistance or ManhattanDistance.

Method Detail

searchR

public List<? extends VecPaired<Vec,Double>> searchR(Vec q)

Performs a search for points within the set radius of the query point.

Parameters:

q - the query point to search near

Returns:

a list of vectors paired with their true distance from the query point that are within the desired radius of the query point

searchR

public List<? extends VecPaired<Vec,Double>> searchR(Vec q,
                                                     boolean approx)

Performs a search for points within the set radius of the query point.

Parameters:

q - the query point to search near

approx - whether or not to return results in the approximate query range

Returns:

a list of vectors paired with their true distance from the query point that are within the desired radius of the query point

getC

public double getC()

Returns the multiplier used on the radius that controls the degree of approximation.

Returns:

the radius approximation multiplier > 1

getRadius

public double getRadius()

Returns the desired approximate radius for which to return results

Returns:

the radius in use

getL

public int getL()

Returns how many separate hash tables have been created for this distance metric.

Returns:

the number of hash tables in use