A Review for Weighted MinHash Algorithms <s> Jaccard Similarity and MinHash <s> Topic or feature extraction is often used as an important step in document classification and text mining. Topics are succinct representation of content in a document collection and hence are very effective when used as content identifiers in peer-to-peer systems and other large scale distributed content management systems. Effective topic extraction is dependent on the accuracy of term clustering that often has to deal with problems like synonymy and polysemy. Retrieval techniques based on spectral analysis like Latent Semantic Indexing (LSI) are often used to effectively solve these problems. Most of the spectral retrieval schemes produce term similarity measures that are symmetric and often, not an accurate characterization of term relationships. Another drawback of LSI is its running time that is polynomial in the dimensions of the m x n matrix, A. This can get prohibitively large for some IR applications. In this paper, we present efficient algorithms using the technique of Locality-Sensitive Hashing (LSH) to extract topics from a document collection based on the asymmetric relationships between terms in a collection. The relationship is characterized by the term co-occurrences and other higher-order similarity measures. Our LSH based scheme can be viewed as a simple alternative to LSI. We show the efficacy of our algorithms via experiments on a set of large documents. An interesting feature of our algorithms is that it produces a natural hierarchical decomposition of the topic space instead of a flat clustering. <s> BIB001 </s> A Review for Weighted MinHash Algorithms <s> Jaccard Similarity and MinHash <s> We describe an ecient procedure for sampling representatives from a weighted set such that the probability that for any weightings S and T, the probability that the two choose the same sample is the Jacard similarity: Pr[sample(S) = sample(T)] = P x min(S(x),T(x)) P x max(S(x),T(x)) . The sampling process takes expected time linear in the number of non-zero weights, independent of the weights themselves. We discuss and develop the implementation of our sampling schemes, reducing the requisite computation substantially, and reducing the randomness required to only four bits in expectation. <s> BIB002 </s> A Review for Weighted MinHash Algorithms <s> Jaccard Similarity and MinHash <s> MinHash and SimHash are the two widely adopted Locality Sensitive Hashing (LSH) algorithms for large-scale data processing applications. Deciding which LSH to use for a particular problem at hand is an important question, which has no clear answer in the existing literature. In this study, we provide a theoretical answer (validated by experiments) that MinHash virtually always outperforms SimHash when the data are binary, as common in practice such as search. The collision probability of MinHash is a function of resemblance similarity (R), while the collision probability of SimHash is a function of cosine similarity (S). To provide a common basis for comparison, we evaluate retrieval results in terms of S for both MinHash and SimHash. This evaluation is valid as we can prove that MinHash is a valid LSH with respect to S, by using a general inequality S 2 <s> BIB003
The bag-of-words model is widely used in many applications, especially document analysis. In this section, we will introduce the Jaccard similarity, which has been successfully applied in the bag-of-words model BIB003 , and the MinHash algorithm, which is a well-known LSH algorithm and used to unbiasedly estimate the Jaccard similarity. Also, we will introduce their corresponding extended versions. Given a universal set U and its subset S ⊆ U, if for any element k ∈ S, its weight S k = 1 and for any element k ∈ U − S, its weight S k = 0, then we call S a binary set; if for any element k ∈ S, S k > 0 and for any element k ∈ U − S, its weight S k = 0, then we call S a weighted set. Furthermore, all (sub)sets can be represented as vectors whose lengths are the size of the universal set, for example, A random permutation π is performed on U, i.e., π : U → U. Considering the high complexity of the random permutation, alternatively, we can uniformly and injectively map each element in U into the real axis, i.e., f : U → R, to approximate the random permutation BIB001 . In other words, each element is assigned with a unique hash value v ∈ R. Figure 1 (a-b) shows the random permutation and uniform mapping on U = {1, 2, 3, 4, 5, 6, 7}, respectively. The values on the real axis in Figure 1 (b) imply that the elements are uniformly mapped to the positions in R, which is equivalent to the random permutation in Figure 1(a) . Furthermore, we can extend uniform mapping on binary sets into weighted sets, i.e., f : (U, Y ) → R, where Y = [0, S k ], which means that each (U k , y k ), where U k ∈ U and y k ∈ Y , is distinct. Next, we can globally apply random permutation or uniform mapping to a subset S of U, as shown in Figure 1(c-d) . In other words, the same random permutation or the same uniform mapping is imposed on the universal set and all its subsets. Furthermore, for a subset S, the most important element is the first one in the leftmost, e.g., 7 in Figure 1(c-d) . From the perspective of functions, taking the first element is considered as a hash function, i.e., h(S) = min(π(S)) for random permutation and h(S) = min(f (S)) for uniform mapping (we adopt π to represent the random permutation and uniform mapping for unity below). If we repeat the process D times, we will obtain a fingerprint with D hash values, i.e., . Now we give two important definitions of the Jaccard similarity and the generalized Jaccard similarity as well as the corresponding solution schemes for the two similarity measures, i.e., the MinHash scheme and the Consistent Weighted Sampling (CWS) scheme. The Jaccard similarity is statistically a measure of comparing the similarity of two binary sets. Definition 5 (Jaccard Similarity). Given two sets S and T , the Jaccard similarity is defined as The above definition assumes that all elements are equally important. If we extend the definition on weighted sets, we will have the generalized Jaccard similarity as follows. Definition 6 (Generalized Jaccard Similarity). Given two , . . . , n}, then the generalized Jaccard similarity is It is very time-consuming to compute the (generalized) Jaccard similarity for all paired sets, especially in the case of the large-scale universal set, due to the inefficient operations of union and intersection. To this end, some efficient LSH algorithms have been successively proposed to approximate the similarity measures. MinHash is used to approximate the Jaccard similarity of two sets. It is proved that the probability of two sets, S and T , to generate the same MinHash value (hash collision) exactly equals the Jaccard similarity of the two sets J(S, T ): However, it is very expensive for a large universal set to generate the explicit random permutations. Therefore, we generally employ the uniform mapping in practice. To this end, a hash function as follows is adopted to produce the permutated index It is easy to see that the MinHash algorithm treats all elements in U equally because each element can be mapped to the minimum hash value with equal probability. However, if the method is directly used for a weighted set, the weights, which imply the importance level of each element, will have to be simply replaced with 1 or 0. Consequently, the approach will give rise to serious information loss. In order to address the aforementioned problem, some weighted MinHash algorithms have been successively proposed, where the Consistent Weighted Sampling (CWS) scheme BIB002 is very remarkable. Sampling [45] ). Given a weighted set S = [S 1 , . . . , S n ], where S k ≥ 0 for k ∈ {1, . . . , n}, Consistent Weighted Sampling (CWS) generates a sample (k, y k ) : 0 ≤ y k ≤ S k , which is uniform and consistent.