A Review for Weighted MinHash Algorithms <s> Experimental Preliminaries <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> Experimental Preliminaries <s> Document sketching using Jaccard similarity has been a workable effective technique in reducing near-duplicates in Web page and image search results, and has also proven useful in file system synchronization, compression and learning applications. Min-wise sampling can be used to derive an unbiased estimator for Jaccard similarity and taking a few hundred independent consistent samples leads to compact sketches which provide good estimates of pairwise-similarity. Subsequent works extended this technique to weighted sets and show how to produce samples with only a constant number of hash evaluations for any element, independent of its weight. Another improvement by Li et al. shows how to speedup sketch computations by computing many (near-)independent samples in one shot. Unfortunately this latter improvement works only for the unweighted case. In this paper we give a simple, fast and accurate procedure which reduces weighted sets to unweighted sets with small impact on the Jaccard similarity. This leads to compact sketches consisting of many (near-)independent weighted samples which can be computed with just a small constant number of hash function evaluations per weighted element. The size of the produced unweighted set is furthermore a tunable parameter which enables us to run the unweighted scheme of Li et al. in the regime where it is most efficient. Even when the sets involved are unweighted, our approach gives a simple solution to the densification problem that other works attempted to address. Unlike previously known schemes, ours does not result in an unbiased estimator. However, we prove that the bias introduced by our reduction is negligible and that the standard deviation is comparable to the unweighted case. We also empirically evaluate our scheme and show that it gives significant gains in computational efficiency, without any measurable loss in accuracy. <s> BIB002
Thirteen state-of-the-art methods, which consist of one standard MinHash algorithm for binary sets and twelve weighted MinHash algorithms for weighted sets, are compared in our experiments: MinHash to the collection of subelements which are generated by explicitly quantizing weighted sets and rounding the remaining float part of the subelements; "# of Docs": size of the data set. "# of Features": size of the dictionary (universal set) of the data set. "Average Density": ratio of the elements with positive weights to all the elements in the universal set (a small value indicates a sparse data set). "Average Mean of Weights": mean of the weights of the documents for each element (a large value indicates that the weights of elements are large BIB001 and BIB002 [46], each weight is scaled up by a factor of 1,000 for the quantization of the subelements. Suppose that each algorithm generates x S and x T , which are the fingerprints with a length of D for the two real-valued weighted sets, S and T , respectively. The similarity between S and T is where 1(state) = 1 if state is true, and 1(state) = 0 otherwise. The above equation calculates the ratio of the same MinHash values (i.e., collision) between x S and x T , which is used to approximate the probability that S and T generate the same MinHash value, and to estimate the generalized Jaccard similarity. We set D, the parameter of the number of hash functions (or random samples), such that D ∈ {10, 20, 50, 100, 120, 150, 200}. All the random variables are globally generated at random in one sampling process, that is, the same elements in different weighted sets share the same set of random variables. All the experiments are conducted on a node of a Linux Cluster with 2 × 2.3 GHz Intel Xeon CPU (64 bit) and 128GB RAM.