A Review for Weighted MinHash Algorithms <s> Improved Consistent Weighted Sampling <s> We present two algorithms for the approximate nearest neighbor problem in high-dimensional spaces. For data sets of size n living in R d , the algorithms require space that is only polynomial in n and d, while achieving query times that are sub-linear in n and polynomial in d. We also show applications to other high-dimensional geometric problems, such as the approximate minimum spanning tree. The article is based on the material from the authors' STOC'98 and FOCS'01 papers. It unifies, generalizes and simplifies the results from those papers. <s> BIB001 </s> A Review for Weighted MinHash Algorithms <s> Improved Consistent Weighted Sampling <s> We propose a new Consistent Weighted Sampling method, where the probability of drawing identical samples for a pair of inputs is equal to their Jaccard similarity. Our method takes deterministic constant time per non-zero weight, improving on the best previous approach which takes expected constant time. The samples can be used as Weighted Minhash for efficient retrieval and compression (sketching) under Jaccard or L1 metric. A method is presented for using simple data statistics to reduce the running time of hash computation by two orders of magnitude. We compare our method with the random projection method and show that it has better characteristics for retrieval under L1. We present a novel method of mapping hashes to short bit-strings, apply it to Weighted Minhash, and achieve more accurate distance estimates from sketches than existing methods, as long as the inputs are sufficiently distinct. We show how to choose the optimal number of bits per hash for sketching, and demonstrate experimental results which agree with the theoretical analysis. <s> BIB002
CWS needs to traverse in both directions for the purpose of the two special "active indices". Subsequently, Ioffe proposed the Improved Consistent Weighted Sampling (ICWS) algorithm BIB002 which can directly sample the two special "active indices", y k and z k . In BIB002 , the two special "active indices" can be obtained via the following equations, where b k ∼ Uniform(0, 1) and r k ∼ Gamma(2, 1). On the other hand, in the algorithmic implementation of ICWS, Eq. (5) is replaced with the following one for the sake of consistency where β k ∼ Uniform(0, 1). It can be proved that ln y k in Eq. (5) and ln y k in Eq. (7) have the same uniform distribution in The floor function and the uniform random variable β k in Eq. (7) ensures that a fixed y k is sampled in an interval of r k . From the perspective of Eq. (4), in this case, ICWS can produce the same y k (i.e., consistency) if the values of S k in different weighted sets change subtly, which makes the collision of (k, y k ) possible and the probability unequal to 0. By contrast, in the case of Eq. (5), different S k definitely generates different y k . In other words, when the weight S k varies in a certain range, Eq. (7) guarantees that y k is independent of the weight S k conditioned on the range and furthermore, Eq. (6) makes y k and z k paired and consistent. We know from the above that ICWS implements consistency in a similar way of CWS. In a unified framework, CWS can be quantized through where r k = 1, while ICWS is done through where r k ∼ Gamma(2, 1). Subsequently, in the two methods, y k and z k are actually produced within the intervals which are shared in the same elements from different weighted sets. When the weight S k fluctuates between y k and z k , y k and z k remain the same, as shown in Figure 5 . Consequently, it is possible for different weights of each element to generate the consistent y k and z k . In order to meet the uniformity of the CWS scheme (i.e., sample k in proportion to S k ), ICWS implicitly makes use of a nice property of the exponential distribution: if each hash value a k of the k -th element is drawn from an exponential distribution parameterized with the corresponding weight, i.e., a k ∼ Exp(S k ), the minimum hash value a k will be sampled in proportion to S k , To this end, ICWS implicitly constructs an exponential distribution parameterized with S k , i.e., a k ∼ Exp(S k ): where c k ∼ Gamma(2, 1). In BIB002 , it has been proved that a k follows the exponential distribution Exp(S k ). Based on Eq. (9), the selected k * -th element is returned via k * = arg min k a k . In addition, it is easy to observe that the hash value of (k, y k ), a k , is unique, and in turn consistency is satisfied. Essentially, ICWS proceeds the sampling process as follows: It first samples y k using Eq. (10), which is derived from Eq. (7). Then the sampled y k , as an independent variable, is fed into Eq. (11), which is derived from Eqs. BIB001 and (9), and outputs a hash value conforming to the exponential distribution parameterized with the corresponding weight S k . ICWS calculates the hash value for each element by employing three random variables (i.e., r k , β k , c k ), and the time and space complexity are both O(3nD) 2 .