A Review for Weighted MinHash Algorithms <s> [Gollapudi et. al., 2006](1) <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> [Gollapudi et. al., 2006](1) <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> [Gollapudi et. al., 2006](1) <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> BIB003
Quantization-based weighted MinHash algorithms compute a hash value for each subelement, which is computationally inefficient in practice. In order to accelerate the computation process, Gollapudi and Panigraphy proposed an efficient weighted MinHash algorithm for integer weighted sets, which is able to skip much unnecessary hash value computation by employing the idea of "active index" BIB002 . The algorithm explores the weights from bottom to top. In the integer weighted set, the weighted element is first quantized into a sequence of subelements, each of which has the length of ∆ = 1 (i.e., the weight of each subelement is ∆ = 1), and then each subelement can be uniformly mapped to the interval [0, 1]. Furthermore, we observe an interesting phenomenon that there exists a subsequence which starts with the subelement at the bottom and whose hash values are monotonically decreasing from bottom to top, and the subelements of the subsequence are called as "active indices". Considering any interval which is composed of two adjacent "active indices" in the subsequence, the hash values of the subelements within the interval are definitely greater than that of the lower endpoint. Consequently, the subsequence can be treated as the Bernoulli trials: "success" is the event that the hash value of a certain subelement is less than that of the lower endpoint, and the probability of success is the hash value of the lower endpoint; "failure" is the event that the hash value of a certain subelement is greater than that of the lower endpoint. Naturally, the number of trials that must be run in order to achieve success, i.e., the length of the interval, can be modeled as the geometric distribution. Based on the idea, the subelements between two adjacent "active indices" can be directly skipped by sampling a skipping interval from the geometric distribution. Take S k in the left part of Figure 3 as an illustration, where we just consider the part below the weight S k : It computes and compares hash value of each subelement from bottom to top. Assuming that for seven subelements, When the algorithm starts from the subelement at the bottom y k1 , in the following steps, it will directly reach y k4 by skipping subelements y k2 and y k3 , because the blue subelements with larger hash values than y k1 can be ignored when one only needs to maintain the minimum hash value v k,y k for the k-th element. Specifically, in the interval [y k1 , y k4 ], the hash value v k,y k4 of the right endpoint y k4 is uniformly distributed on the interval [0, v k,y k1 ], and thus the number of subelements within this interval conforms to a geometric distribution with the parameter being v k,y k1 . Similarly, the algorithm directly goes from y k4 to y k6 while skipping subelements y k5 . Since there exist no subelements, whose hash value is smaller than that of y k6 between y k6 and S k , the algorithm ceases to traverse in the element. Consequently, the method can iteratively sample all the "active indices" from bottom to top for the sake of (k, y k ) with the minimum hash value. It is easy to see that y k is the largest "active index" in {1, 2, . . . , S k }. Essentially, the method is not able to change the underlying uniform distribution of the minimum hash value among the subelements generated from the weighted set according to the properties of the Bernoulli trials and the geometric distribution. Therefore, it can be considered as the accelerated version of [Haveliwala et Figure 3 that the method traverses all "active indices" within the weight, i.e, [0, S k ], while skipping nonactive subelements. Consequently, the method remarkably reduces the computational complexity from O( k S k ) to O( k log S k ). However, for real-valued weighted sets, the method still needs an explicit quantization by multiplying a large constant C, which brings tremendous overhead in both time and space. BIB002 ] (1) is still inefficient for real-valued weighted sets because it is actually a weighted MinHash algorithm for integer weighted sets, and real-valued weights have to be transformed into integer weights by multiplying a large constant C, thus increasing the number of "active indices" which need to be traversed. To this end, by setting the weight of the subelement ∆ → 0, the Consistent Weighted Sampling scheme BIB003 was proposed to address the issue that BIB002 (1) cannot directly handle realvalued weights. As is known from Definition 8, the CWS scheme requires two conditions: uniformity and consistency. Uniformity means that each subelement is mapped to the minimum hash value with equal probability. On the other hand, in essence, consistency points out that in a hashing process, the same subelements from different weighted sets are assigned with the same hash value, i.e., global mapping in Figure  1 . If we refer to the decomposition steps of BIB001 , in order to find the "active index" of a certain element that has the minimum hash value, a sequence of "active indices" are shared in the same elements of different weighted sets and independent of the weights, as shown in Figure 4 .