A Review for Weighted MinHash Algorithms <s> Locality Sensitivity Hashing <s> Given two documents A and B we define two mathematical notions: their resemblance r(A, B) and their containment c(A, B) that seem to capture well the informal notions of "roughly the same" and "roughly contained." The basic idea is to reduce these issues to set intersection problems that can be easily evaluated by a process of random sampling that can be done independently for each document. Furthermore, the resemblance can be evaluated using a fixed size sample for each document. This paper discusses the mathematical properties of these measures and the efficient implementation of the sampling process using Rabin (1981) fingerprints. <s> BIB001 </s> A Review for Weighted MinHash Algorithms <s> Locality Sensitivity Hashing <s> We present two algorithms for the approximate nearest neighbor problem in high-dimensional spaces. For data sets of size n living in R d , the algorithms require space that is only polynomial in n and d, while achieving query times that are sub-linear in n and polynomial in d. We also show applications to other high-dimensional geometric problems, such as the approximate minimum spanning tree. The article is based on the material from the authors' STOC'98 and FOCS'01 papers. It unifies, generalizes and simplifies the results from those papers. <s> BIB002 </s> A Review for Weighted MinHash Algorithms <s> Locality Sensitivity Hashing <s> We define and study the notion of min-wise independent families of permutations. We say that F?Sn (the symmetric group) is min-wise independent if for any set X?n and any x?X, when ? is chosen at random in F we havePr(min{?(X)}=?(x))=1|X| . In other words we require that all the elements of any fixed set X have an equal chance to become the minimum element of the image of X under ?. Our research was motivated by the fact that such a family (under some relaxations) is essential to the algorithm used in practice by the AltaVista web index software to detect and filter near-duplicate documents. However, in the course of our investigation we have discovered interesting and challenging theoretical questions related to this concept?we present the solutions to some of them and we list the rest as open problems. <s> BIB003 </s> A Review for Weighted MinHash Algorithms <s> Locality Sensitivity Hashing <s> (MATH) A locality sensitive hashing scheme is a distribution on a family $\F$ of hash functions operating on a collection of objects, such that for two objects x,y, PrheF[h(x) = h(y)] = sim(x,y), where sim(x,y) e [0,1] is some similarity function defined on the collection of objects. Such a scheme leads to a compact representation of objects so that similarity of objects can be estimated from their compact sketches, and also leads to efficient algorithms for approximate nearest neighbor search and clustering. Min-wise independent permutations provide an elegant construction of such a locality sensitive hashing scheme for a collection of subsets with the set similarity measure sim(A,B) = \frac{|A P B|}{|A P Ehe\F [d(h(P),h(Q))] x O(log n log log n). EMD(P, Q). . <s> BIB004 </s> A Review for Weighted MinHash Algorithms <s> Locality Sensitivity Hashing <s> In the past 10 years, new powerful algorithms based on efficient data structures have been proposed to solve the problem of Nearest Neighbors search (or Approximate Nearest Neighbors search). If the Euclidean Locality Sensitive Hashing algorithm, which provides approximate nearest neighbors in a euclidean space with sublinear complexity, is probably the most popular, the euclidean metric does not always provide as accurate and as relevant results when considering similarity measure as the Earth-Mover Distance and χ2 distances. In this paper, we present a new LSH scheme adapted to χ2 distance for approximate nearest neighbors search in high-dimensional spaces. We define the specific hashing functions, we prove their local-sensitivity, and compare, through experiments, our method with the Euclidean Locality Sensitive Hashing algorithm in the context of image retrieval on real image databases. The results prove the relevance of such a new LSH scheme either providing far better accuracy in the context of image retrieval than euclidean scheme for an equivalent speed, or providing an equivalent accuracy but with a high gain in terms of processing speed. <s> BIB005
One fundamental research topic in data mining and machine learning is data similarity (or distance) computation. Based on data similarity, one can further conduct classification, clustering, regression, retrieval and visualization, etc. So far some classical similarity (or distance) measures have been adopted, e.g., l p distance, cosine similarity, hamming distance and Jaccard similarity, etc. The problem of similarity computation is defined as the nearest neighbor (NN) problem as follows. Definition 1 (Nearest Neighbor). Given a query object q, the goal is to find an object NN(q), called nearest neighbor, from a set of objects P = {p 1 , p 2 , · · · , p N } so that NN(q) = arg min p∈P dist(q, p), where dist(q, p) is a distance between q and p. Alternatively, there exists a variant of the nearest neighbor problem, i.e., the fixed-radius near neighbor (R-NN). Definition 2 (R-Near Neighbor). Given a query object q and the distance threshold R, the goal is to find all objects R-NN(q) from a set of objects Finding the nearest neighbor or R-near neighbors can be easily solved in the case of low-dimensional data. However, some efficient algorithms for them in low-dimensional spaces will spend high computational cost in the highdimensional settings due to curse of dimensionality. To this end, a large amount of research has concentrated on the approximation problem. Cosine similarity SimHash BIB004 Jaccard similarity MinHash BIB003 , BIB001 Hamming distance BIB002 ] BIB002 χ 2 distance χ 2 -LSH BIB005 Definition 3 (c-Approximate Near Neighbor). Given a query object q, the distance threshold R > 0, 0 < δ < 1 and c ≥ 1, the goal is to report some cR-near neighbor of q with the probability of 1 − δ if there exists an R-near neighbor of q from a set of objects One well-known solution scheme for c-Approximate Near Neighbor is Locality Sensitivity Hashing (LSH), which aims to map similar data objects to the same data points represented as the hash codes with a higher probability than the dissimilar ones by employing a family of randomized hash functions. Formally, an LSH algorithm is defined as follows: