A Review for Weighted MinHash Algorithms <s> Experimental Results <s> Clustering is one of the most crucial techniques for dealing with the massive amount of information present on the web. Clustering can either be performed once offline, independent of search queries, or performed online on the results of search queries. Our offline approach aims to efficiently cluster similar pages on the web, using the technique of Locality-Sensitive Hashing (LSH), in which web pages are hashed in such a way that similar pages have a much higher probability of collision than dissimilar pages. Our preliminary experiments on the Stanford WebBase have shown that the hash-based scheme can be scaled to millions of urls. <s> BIB001 </s> A Review for Weighted MinHash Algorithms <s> Experimental Results <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> BIB002 </s> A Review for Weighted MinHash Algorithms <s> Experimental Results <s> A modular drywall is erected wherein a metallic framework is initially formed including spaced vertical rails integrally and orthogonally mounting respective horizontal and vertical rails at upper and lower terminal ends respectively of the vertical rails. Drywall panels are subsequently fastened to forwardly projecting ends of the framework and subsequently filler strips are provided wherein the filler strips are formed to encompass and bridge gaps between drywall panels. The filler strips include a planar forward strip mouting a rearwardly extending longitudinally aligned projecting strip with a magnetic strip mounted to a rear end surface of the projecting strip to secure each filler strip to an associated metallic rail. <s> BIB003 </s> A Review for Weighted MinHash Algorithms <s> Experimental Results <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> BIB004 </s> A Review for Weighted MinHash Algorithms <s> Experimental Results <s> We develop 0-bit consistent weighted sampling (CWS) for efficiently estimating min-max kernel, which is a generalization of the resemblance kernel originally designed for binary data. Because the estimator of 0-bit CWS constitutes a positive definite kernel, this method can be naturally applied to large-scale data mining problems. Basically, if we feed the sampled data from 0-bit CWS to a highly efficient linear classifier (e.g., linear SVM), we effectively (and approximately) train a nonlinear classifier based on the min-max kernel. The accuracy improves as we increase the sample size. In this paper, we first demonstrate, through an extensive classification study using kernel machines, that the min-max kernel often provides an effective measure of similarity for nonnegative data. This helps justify the use of min-max kernel. However, as the min-max kernel is nonlinear and might be difficult to be used for industrial applications with massive data, we propose to linearize the min-max kernel via 0-bit CWS, a simplification of the original CWS method. The previous remarkable work on {\em consistent weighted sampling (CWS)} produces samples in the form of (i*, t*) where the i* records the location (and in fact also the weights) information analogous to the samples produced by classical minwise hashing on binary data. Because the t* is theoretically unbounded, it was not immediately clear how to effectively implement CWS for building large-scale linear classifiers. We provide a simple solution by discarding t* (which we refer to as the "0-bit" scheme). Via an extensive empirical study, we show that this 0-bit scheme does not lose essential information. We then apply 0-bit CWS for building linear classifiers to approximate min-max kernel classifiers, as extensively validated on a wide range of public datasets. We expect this work will generate interests among data mining practitioners who would like to efficiently utilize the nonlinear information of non-binary and nonnegative data. <s> BIB005 </s> A Review for Weighted MinHash Algorithms <s> Experimental Results <s> Weighted minwise hashing (WMH) is one of the fundamental subroutine, required by many celebrated approximation algorithms, commonly adopted in industrial practice for large -scale search and learning. The resource bottleneck with WMH is the computation of multiple (typically a few hundreds to thousands) independent hashes of the data. We propose a simple rejection type sampling scheme based on a carefully designed red-green map, where we show that the number of rejected sample has exactly the same distribution as weighted minwise sampling. The running time of our method, for many practical datasets, is an order of magnitude smaller than existing methods. Experimental evaluations, on real datasets, show that for computing 500 WMH, our proposal can be 60000x faster than the Ioffe's method without losing any accuracy. Our method is also around 100x faster than approximate heuristics capitalizing on the efficient ``densified" one permutation hashing schemes~\cite{Proc:OneHashLSH_ICML14,Proc:Shrivastava_UAI14}. Given the simplicity of our approach and its significant advantages, we hope that it will replace existing implementations in practice. <s> BIB006 </s> A Review for Weighted MinHash Algorithms <s> Experimental Results <s> Min-Hash, as a member of the Locality Sensitive Hashing (LSH) family for sketching sets, plays an important role in the big data era. It is widely used for efficiently estimating similarities of bag-of-words represented data and has been extended to dealing with multi-sets and real-value weighted sets. Improved Consistent Weighted Sampling (ICWS) has been recognized as the state-of-the-art for real-value weighted Min-Hash. However, the algorithmic implementation of ICWS is flawed because it violates the uniformity of the Min-Hash scheme. In this paper, we propose a Canonical Consistent Weighted Sampling (CCWS) algorithm, which not only retains the same theoretical complexity as ICWS but also strictly complies with the definition of Min-Hash. The experimental results demonstrate that the proposed CCWS algorithm runs faster than the state-of-the-arts while achieving similar classification performance on a number of real-world text data sets. <s> BIB007
We empirically present the mean square errors (MSEs) of the estimators of the generalized Jaccard similarity by comparing the estimation results from the compared methods and the real generalized Jaccard similarity calculated using Eq. (2), and runtime of encoding each data set into fingerprints. We repeat each experiment 10 times and compute the mean and the standard derivation of the results. Figure 8 and Figure 9 report the mean square errors (MSEs) of the estimators of the generalized Jaccard similarity from 13 compared methods, and their runtime, respectively. Generally, MinHash performs worst but runs faster than most of algorithms because it simply discards the auxiliary weight information of elements. BIB004 performs nearly the same as BIB001 in terms of accuracy so that they cannot be distinguished. This is largely because the two algorithms both completely Note that in the experiment, each algorithm is given a cutoff of 24 hours. BIB006 is forced to stop due to running overtime on Syn3A0.2B. preserve the integer parts of elements and the float parts trivially impact the estimators. Also, the two methods maintain the same empirical time level. "Active index"-based algorithms not only give more accurate estimators, but also remarkably improve efficiency of the above methods by sampling several and even only two special subelements called "active indices". Compared with BIB001 , BIB002 (1) is actually an accelerated version: It transforms a weighted set into a binary set by employing the same preprocessing as BIB001 , i.e, multiplying by a large constant, and then in each element iteratively generates "active indices" whose number is less than the value of the augmented weight, thus improving the efficiency of BIB001 and BIB002 (1), as shown in Figure 9 . Obviously, the time complexity of BIB002 (1) is closely related to the large constant, and it can be further enhanced. It performs the same as BIB001 and BIB004 in terms of accuracy so that their curves cannot be distinguished in Figure 8 . By contrast, the Consistent Weighted Sampling (CWS) scheme, as an important category of the real-value weighted MinHash algorithms, can directly handle with real-valued weighted sets. The CWS algorithm, as the first proposed method of the CWS scheme, generally performs best but runs very slowly, possibly because the algorithm iterates many times in order to find the y k as well as z k for CWS. Furthermore, the iteration process happens on real values instead of integers, which further increases the number of iterations, because the number of real values to explore is infinite. ICWS performs almost the same performance as 0-bit CWS in terms of accuracy and runtime since one component of ICWS, y k , is trivial to approximate Eq. (2) for most data sets, which has been experimentally verified in BIB005 . PCWS improves ICWS in terms of accuracy and runtime by adopting one less number of uniform random variables than ICWS. I 2 CWS obtains similar accuracy with CWS in most cases and meanwhile, defeats other CWSbased algorithms, which demonstrates that I 2 CWS is able to better approximate Eq. (2) by fixing the dependence problem of ICWS, but it increases a little time cost. Also, we would like to note that the accuracy performance gain of I 2 CWS is clear in the case of small D, which implies that I 2 CWS is powerful in the scenarios of limited computational and spatial budget. In terms of accuracy, CCWS is inferior to all other CWSbased algorithms because CCWS uniformly discretizes the original weights instead of discretizing the logarithm of the weights in ICWS, 0-bit CWS, PCWS and I 2 CWS. It is worth noting that the performance of CCWS is getting worse with the increase of the variance of weights of data sets. As shown in BIB007 , taking a logarithm on the weights generates an increased probability of collision, and thus CCWS is suitable to data sets with small variance. Surprisingly, CCWS runs more efficiently than ICWS, 0-bit CWS, PCWS and I 2 CWS because the former directly adopts variables from the Beta distribution and the Gamma distribution instead of the Uniform distribution as the latter do. The accuracy gap between [Gollapudi et Fig. 9 . Runtime on the synthetic weighted sets with powerlaw distributions. The x-axis denotes the length of fingerprints, D. Note that in the experiment, each algorithm is given a cutoff of 24 hours. BIB006 is forced to stop due to running overtime on Syn3A0.2B. MinHash narrows down with D increasing, which largely results from the accumulated errors. In terms of runtime, BIB002 (2) performs worse because it has to scan the set twice. BIB006 (2), which has been proved to exactly estimate Eq. (2), shows good performance in terms of accuracy and runtime except for Syn3A0.2B. The high efficiency is due to the fact that BIB006 (2) only makes use of a small number of samples, while it fails on Syn3A0.2B, possibly due to the small weights. In this case, small weights make the value of s x = n k=1 S k n k=1 max(S k ) 3 small, where max(S k ) represents the maximum weight (i.e., the upper bound) of each element in the whole data set, thus decelerating the algorithm. However, we would like to note that it is infeasible to obtain the upper bound of the weight of each element in practice, and thus the method is limited in applying to the real-world problems. BIB003 performs worse than most of the weighted MinHash algorithms since it just biasedly estimates Eq. (2), but it runs very fast by simply computation for each element, i.e, Eq. (28).