A Review for Weighted MinHash Algorithms <s> Canonical Consistent Weighted Sampling <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> BIB001 </s> A Review for Weighted MinHash Algorithms <s> Canonical Consistent Weighted Sampling <s> Motivated by structural properties of the Web graph that support efficient data structures for in memory adjacency queries, we study the extent to which a large network can be compressed. Boldi and Vigna (WWW 2004), showed that Web graphs can be compressed down to three bits of storage per edge; we study the compressibility of social networks where again adjacency queries are a fundamental primitive. To this end, we propose simple combinatorial formulations that encapsulate efficient compressibility of graphs. We show that some of the problems are NP-hard yet admit effective heuristics, some of which can exploit properties of social networks such as link reciprocity. Our extensive experiments show that social networks and the Web graph exhibit vastly different compressibility characteristics. <s> BIB002 </s> A Review for Weighted MinHash Algorithms <s> Canonical Consistent Weighted Sampling <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> BIB003
ICWS directly samples y k via Eq. (7), which essentially conducts an implicit quantization. However, in Eq. (7), there exists the logarithm transformation, i.e., ln y k and ln S k , which means that the implicit quantization actually occurs on the logarithm of the original weights and in turn gives rise to non-uniform sampling on the original weights. Consequently, in BIB003 , Wu et. al. argue that ICWS violates the uniformity property of the MinHash scheme, as shown in Figure 6 , and the Canonical Consistent Weighted Sampling (CCWS) algorithm was proposed to avoid the risk of violating the uniformity property of the MinHash scheme. In CCWS, Eq. (5) is replaced with the following equation where b k ∼ Uniform(0, 1). The above equation effectively avoids scaling the weight sublinearly. Similarly, to implicitly quantize the weights in its algorithmic implementation, Wu et. al. adopt the following equation where β k ∼ Uniform(0, 1). Eq. BIB002 shows that the quantization is directly conducted on the original weight S k . Also, Eq. (6) is replaced with where r k ∼ Beta(2, 1). To implement uniformity, CCWS utilizes the property of the exponential distribution, Eq. (8), and constructs the exponential distribution via Eq. BIB001 . CCWS adopts the same framework of ICWS to satisfy uniformity and consistency: uniformity is implemented via the property of the exponential distribution, and consistency is fulfilled by generating consistent y k and z k and uniquely assigning a hash value to (k, y k ). Although CCWS preserves the uniformity property by uniformly discretizing the original weights, it decreases the probability of collision and thus generally performs worse than ICWS. On the other hand, we would like to note that there exists limitation in the process of quantization: , which can be appropriately solved by scaling the weight.