[Home] DMelt member access. Java source code: jsat.linear.vectorcollection.lsh.E2LSH
package jsat.linear.vectorcollection.lsh;
import java.util.List;
import jsat.distributions.Normal;
import jsat.linear.Vec;
import static java.lang.Math.*;
import java.util.*;
import jsat.linear.DenseVector;
import jsat.linear.VecPaired;
import jsat.linear.VecPairedComparable;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.linear.distancemetrics.ManhattanDistance;
import jsat.utils.IntList;
import jsat.utils.IntSet;
import jsat.utils.random.RandomUtil;
/**
* This is an implementation of Locality Sensitive Hashing for the
* {@link ManhattanDistance L1} and
* {@link EuclideanDistance 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 {@link #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
*/
public class E2LSH
{
private List vecs;
private DistanceMetric dm;
private double radius;
private double eps;
private double p1;
private double p2;
private int w;
private double c;
/**
* 1-delta is the probability of correctly selecting the neighbors within
* radius R
*/
private double delta = Double.NaN;
private int L;
private int k;
private List distCache;
private Vec[][] h;
private double[][] b;
private List
Ads help maintain this website.