A Review for Weighted MinHash Algorithms <s> [Chum et. al., 2008] <s> A modular drywall is erected wherein a metallic framework is initially formed including spaced vertical rails integrally and orthogonally mounting respective horizontal and vertical rails at upper and lower terminal ends respectively of the vertical rails. Drywall panels are subsequently fastened to forwardly projecting ends of the framework and subsequently filler strips are provided wherein the filler strips are formed to encompass and bridge gaps between drywall panels. The filler strips include a planar forward strip mouting a rearwardly extending longitudinally aligned projecting strip with a magnetic strip mounted to a rear end surface of the projecting strip to secure each filler strip to an associated metallic rail. <s> BIB001 </s> A Review for Weighted MinHash Algorithms <s> [Chum et. al., 2008] <s> Locality Sensitive Hash functions are invaluable tools for approximate near neighbor problems in high dimensional spaces. In this work, we are focused on LSH schemes where the similarity metric is the cosine measure. The contribution of this work is a new class of locality sensitive hash functions for the cosine similarity measure based on the theory of concomitants, which arises in order statistics. Consider <i>n</i> i.i.d sample pairs, {(<i>X</i><sub>1</sub>; <i>Y</i><sub>1</sub>); (<i>X</i><sub>2</sub>; <i>Y</i><sub>2</sub>); : : : ;(<i>X</i><sub><i>n</i></sub>; <i>Y</i><sub><i>n</i></sub>)} obtained from a bivariate distribution <i>f</i>(<i>X, Y</i>). Concomitant theory captures the relation between the order statistics of <i>X</i> and <i>Y</i> in the form of a rank distribution given by Prob(Rank(<i>Y</i><sub>i</sub>)=<i>j</i>-Rank(Xi)=<i>k</i>). We exploit properties of the rank distribution towards developing a locality sensitive hash family that has excellent collision rate properties for the cosine measure. ::: The computational cost of the basic algorithm is high for high hash lengths. We introduce several approximations based on the properties of concomitant order statistics and discrete transforms that perform almost as well, with significantly reduced computational cost. We demonstrate the practical applicability of our algorithms by using it for finding similar images in an image repository. <s> BIB002
Chum et. al. BIB001 proposed a simple weighted MinHash algorithm which combines quantization and sampling. Similar to other quantization-based algorithms, each weighted element can be quantized into a number of distinct and equal-sized subelements, e.g., S (i) k , i ∈ {1, 2, · · · , S k } in the case that S k is a positive integer. Subsequently, each subelement is assumed to be assigned with a hash value, e.g., f (S (i) k ) ∼ Uniform(0, 1). Naturally, the MinHash value of the k-th element is h(S k ) = min{f (S Finally, h(S k ) can be expressed as where x ∼ Uniform(0, 1). Interestingly, Eq. (28) can be directly used for realvalued weighted sets without multiplying a large constant. U1+U2  U1+U2+U3  U1+U2+U3+U4  U1+U2+U3+U4+U5   S  S1  S2  S3  S4  S5   0  U1  U1+U2  U1+U2+U3  U1+U2+U3+U4  U1+U2+U3+U4+U5   T  T1  T2  T3  T4  T5 Fig . 7 . A toy example of Red-Green partition on S and T . U i represents the maximum weight of each element in the universal set U , and the length of the green area does the weight of each element, i.e., S i and Also, we observe that the approach essentially samples an element proportionally to its weight because Eq. (28) is an exponential distribution with parameter being S k , i.e., , as shown in Eq. (19), and also, the sampled subelement is used to supersede the whole element. Apparently, the exponential distribution makes each element sampled proportionally to its weight, so it is unnecessary to deduce Eq. (28) from Eq. BIB002 . The Chum's algorithm, ICWS and its variations all employ the exponential distribution so that each element is selected proportionally to its weight. However, the algorithm only offers a biased estimate to the generalized Jaccard similarity since it cannot satisfy the consistency. Superficially, compared with ICWS and its variations, the algorithm just returns k, that is, no y k , and thus the specific subelement cannot be positioned. Essentially, the sampled subelement does not depend on the interval but the weight, and thus once the weight fluctuates, the sampled subelement will change. This is possibly because each subelement from the same elements might be mapped to different hash values in different weighted sets in the case of no explicit function.