A Review for Weighted MinHash Algorithms <s> Consistent Weighted Sampling <s> We define and study the notion of min-wise independent families of permutations. We say that F?Sn (the symmetric group) is min-wise independent if for any set X?n and any x?X, when ? is chosen at random in F we havePr(min{?(X)}=?(x))=1|X| . In other words we require that all the elements of any fixed set X have an equal chance to become the minimum element of the image of X under ?. Our research was motivated by the fact that such a family (under some relaxations) is essential to the algorithm used in practice by the AltaVista web index software to detect and filter near-duplicate documents. However, in the course of our investigation we have discovered interesting and challenging theoretical questions related to this concept?we present the solutions to some of them and we list the rest as open problems. <s> BIB001 </s> A Review for Weighted MinHash Algorithms <s> Consistent Weighted Sampling <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> Consistent Weighted Sampling <s> For implementing content management solutions and enabling new applications associated with data retention, regulatory compliance, and litigation issues, enterprises need to develop advanced analytics to uncover relationships among the documents, e.g., content similarity, provenance, and clustering. In this paper, we evaluate the performance of four syntactic similarity algorithms. Three algorithms are based on Broder's "shingling" technique while the fourth algorithm employs a more recent approach, "content-based chunking". For our experiments, we use a specially designed corpus of documents that includes a set of "similar" documents with a controlled number of modifications. Our performance study reveals that the similarity metric of all four algorithms is highly sensitive to settings of the algorithms' parameters: sliding window size and fingerprint sampling frequency. We identify a useful range of these parameters for achieving good practical results, and compare the performance of the four algorithms in a controlled environment. We validate our results by applying these algorithms to finding near-duplicates in two large collections of HP technical support documents. <s> BIB003
The first algorithm of the Consistent Weighted Sampling scheme, the Consistent Weighted Sampling (CWS) algorithm, extends "active indices" from [0, S k ] in BIB002 (1) to [0, +∞). As shown in the right part of Figure 3 , a sequence of "active indices" are composed of y k1 , y k4 , y k6 , y k10 and y k15 , although y k10 and y k15 are above the weight S k . It is easy for us to observe two special "active indices", one of which is the largest "active index" y k = y k6 ∈ [0, S k ] smaller than the weight and the other of which is the smallest "active index" z k = y 10 ∈ (S k , +∞) greater than the weight. In order to find the two "active indices", instead of starting from 0 in BIB002 (1), CWS explores the "active indices" in both directions from the weight S k , towards 0 as well as +∞. Inspired by the fact that the "active indices" are uniformly and independently sampled in BIB002 (1), the distribution over "active indices" in any interval is independent from the one over "active indices" in another disjoint interval. Consequently, CWS partitions (0, +∞) into intervals of the form (2 k−1 , 2 k ] so that the "active indices" can be explored in each interval independently. In other words, one can leap directly to any interval and explore "active indices" within it. Specifically, in each interval, one starts from the upper endpoint of the interval, and generates a sequence of "active indices" from the upper endpoint to the lower one by uniformly sampling. So the "active indices" are independent  Note that y k and z k are two special "active indices": The former denotes the largest "active index" smaller than the weight, while the latter is the smallest "active index" greater than the weight. BIB002 (1) proceeds traversing "active indices", y k1 , y k4 and y k6 , below the weight S k , from bottom to top by sampling a skipping interval from the geometric distribution. By contrast, CWS successively explores the intervals in both directions of the interval  BIB001 containing S k until y k and z k are found. A sequence of "active indices", e.g., y k1 , y k4 , y k6 , y k10 , y k15 , y k19 , y k25 , are shared in the k-th elements of different weighted sets, e.g., S, T and R, and independent of the weights, e.g., S k , T k and R k . of the specific weight and the sampling operation satisfies the uniformity property of the CWS scheme. In terms of consistency, the "active indices" are deduced from the upper endpoints of the intervals, which are shared in the same elements from different weighted sets. Consequently, the two special "active indices", y k and z k , are consistent and paired, which means that the same y k corresponds to the same z k , and vice versa. In addition, the hash value of (k, y k ) is just related to z k , and thus in the same elements from different weighted set, the same (k, y k ) can be consistently mapped to the same hash value. CWS starts with the interval containing S k , and if y k or z k is not found, it will seek in the next corresponding interval until it is observed. As shown in Figure 3 , CWS first seeks y k and z k in the interval  BIB001 . y k = y k6 is found, and thus CWS stops traversing towards 0. However, z k is not in this interval, which makes CWS explore in the next interval BIB001 BIB003 . Consequently, z k = y 10 is obtained and CWS stops towards +∞. CWS runs in expected constant time to find y k and z k , and thus its average time complexity is O( k log S k ).