A Review for Weighted MinHash Algorithms <s> Practical Consistent Weighted Sampling <s> Minwise hashing is a standard procedure in the context of search, for efficiently estimating set similarities in massive binary data such as text. Recently, 6-bit minwise hashing has been applied to large-scale learning and sublinear time near-neighbor search. The major drawback of minwise hashing is the expensive preprocessing, as the method requires applying (e.g.,) k = 200 to 500 permutations on the data. This paper presents a simple solution called one permutation hashing. Conceptually, given a binary data matrix, we permute the columns once and divide the permuted columns evenly into k bins; and we store, for each data vector, the smallest nonzero location in each bin. The probability analysis illustrates that this one permutation scheme should perform similarly to the original (k-permutation) minwise hashing. Our experiments with training SVM and logistic regression confirm that one permutation hashing can achieve similar (or even better) accuracies compared to the k-permutation scheme. See more details in arXiv:1208.1259. <s> BIB001 </s> A Review for Weighted MinHash Algorithms <s> Practical Consistent Weighted Sampling <s> Min-Hash, which is widely used for efficiently estimating similarities of bag-of-words represented data, plays an increasingly important role in the era of big data. It has been extended to deal with real-value weighted sets -- Improved Consistent Weighted Sampling (ICWS) is considered as the state-of-the-art for this problem. In this paper, we propose a Practical CWS (PCWS) algorithm. We first transform the original form of ICWS into an equivalent expression, based on which we find some interesting properties that inspire us to make the ICWS algorithm simpler and more efficient in both space and time complexities. PCWS is not only mathematically equivalent to ICWS and preserves the same theoretical properties, but also saves 20% memory footprint and substantial computational cost compared to ICWS. The experimental results on a number of real-world text data sets demonstrate that PCWS obtains the same (even better) classification and retrieval performance as ICWS with 1/5~1/3 reduced empirical runtime. <s> BIB002
ICWS employs three random variables (i.e., r k , β k , c k ) for each element. Due to the fact that random variables are derived from the uniform random ones in programming languages, it essentially generates five uniform random variables for each element, i.e., , where u k1 , u k2 , v k1 , v k2 ∼ Uniform(0, 1). Inspired by this, Wu et. al. proposed a more efficient algorithm, the Practical Consistent Weighted Sampling (PCWS) algorithm BIB002 , by transforming the original form Eq. (11) for sampling a k in ICWS into an equivalent version and then simplifying it. Taking into consideration r k = − ln(u k1 u k2 ) ∼ Gamma(2, 1) and c k = − ln(v k1 v k2 ) ∼ Gamma(2, 1), where u k1 , u k2 , v k1 , v k2 ∼ Uniform(0, 1), Eq. (11) can be rewritten as In BIB002 , Wu et. al. has proved that and whereŜ k is an unbiased estimator for S k , andŜ k = y k u −1 k1 . Consequently, Eq. (16) can be simplified as where x k ∼ Uinform(0, 1), and Also, Eq. (7) can be rewritten as The only difference between ICWS and PCWS lies in the specific implementation of uniformity, although they both employ the property of exponential distribution. The former adopts Eq. (15), which is equivalent to Eq. (9), while the latter uses Eq. BIB001 . We know from Eqs. BIB001 and (20) that PCWS just employs four uniform random variables for each element, i.e., u k1 , u k2 , β k and x k . Obviously, the time and space complexity of PCWS are both O(4nD), while the time and space complexity of ICWS are essentially O(5nD). Also, the authors shows that PCWS is more efficient empirically than ICWS.