C-MinHash: Improving Minwise Hashing with Circulant Permutation
Authors: Xiaoyun Li
Ping Li
Venue: ICLR 2022 Submitted (2022)

Abstract: Minwise hashing (MinHash) is an important and practical algorithm for generating random hashes to approximate the Jaccard (resemblance) similarity in massive binary (0/1) data. The basic theory of MinHash requires applying hundreds or even thousands of independent random permutations to each data vector in the dataset, in order to obtain reliable results for (e.g.,) building large-scale learning models or approximate near neighbor search in massive data. In this paper, we propose {\bf Circulant MinHash (C-MinHash)} and provide the surprising theoretical results that using only \textbf{two} independent random permutations in a circulant manner leads to uniformly smaller Jaccard estimation variance than that of the classical MinHash with $K$ independent permutations. Experiments are conducted to show the effectiveness of the proposed method. We also analyze a more convenient C-MinHash variant which reduces two permutations to just one, with extensive numerical results to validate that it achieves essentially the same estimation accuracy as using two permutations with rigorous theory.


Under review as a conference paper at ICLR 2022
C-MINHASH: IMPROVING MINWISE HASHING WITH CIRCULANT PERMUTATION
Anonymous authors Paper under double-blind review
ABSTRACT
Minwise hashing (MinHash) is important and practical algorithm for generat- ing random hashes to approximate the Jaccard (resemblance) similarity in mas- sive binary (0/1) data. The basic theory of MinHash requires applying hundreds or even thousands independent random permutations to each data vector in the dataset, in order obtain reliable results for (c.g..) building large-scale learning models or approximate near neighbor search in massive data. In this paper, we propose Circulant MinHash (C-MinHaash) and provide the surprising theoret- ical results that using only two independent random permutations in circulant manner leads to uniformly smaller Jaccard estimation variance than that of the classical MinHash with K independent permutations. Experiments are conducted to show the effectiveness of the proposed method. We also analyze more conve- nient C-MinHash variant which reduces two permutations just one, with exten- sive numerical results to validate that achieves essentially the same estimation accuracy using two permutations with rigorous theory.
INTRODUCTION
Given two D-dimensional binary vectors w E [0, the Jaccard similarity is defined as
J(, Eb 1f = = 1} Σ 1(0, + w; 2 1}
(1)
which is a commonly used similarity metric in machine learning and web search applications. The vectors v and w can also be viewed as two sets of items (which represent the locations of non-zero entries), the Jaccard similarity can be equivalently viewed the size of set intersection of set union. The well-known method of "minwise hashing" (MinHash) (Broder, 1997: Broder et al., 1997; 1998; Li & Church, 2005; Li & König, 201 a standard technique for compurigg/etimaaing the Jaccard similarity in massive binary datasets, with numerous applications such as near neighbor search, duplicate detection, malware detection, web search, clustering. large-scale learning, social networks, computer vision, etc. (Charikar, 2002; Fetterly et al., 2003; Henzinger, 2006; Das et al., 2007: Buchrer Chellapilla, 2008: Bendersky & Croft, 2009: Chierichetti et al., 2009; Lee al., 2010; Li et al., 2011; Deng et al., 2012; Chum & Matas, 2012; Shrivastava & Li, 2012; He et al., 2013; Tamersoy et al., 2014; Shrivastava & Li, 2014; Zamora al., 2016).
the size
1.1 A REVIEW OF MINWISE HASHING (MINHASH)
Algorithm Minwise-hashing (MinHash)
Input: Binary data vector {0, 1)
K independent permutations , ox: [D] + [D].
Output: K hash values h1 (v), hx (w).
For k = to K
hy(v) <- min T (i)
End For

---

Under review as a conference paper at ICLR 2022
For simplicity, Algorithm 1 considers just one vector v E {0, P. In order to generate K hash val- ues for v, we assume K independent permutations: T1,..., TK [D] + [D]. For each permutation, the hash value is the first non-zero location in the permuted vector, i... hg(v) min { vk L,.., K. Similarly, for another binary vector w {0, 1) using the same K permutations, we can also obtain K hash values, (w) The estimator of Jv, w) is simply
K 1(x((0) hg(w))
(V w) =
1 K
Σ
where 1(-} is the indicator function. By fundamental probability and the independence among the permutations, it is easy to show that
Var[Jan] J(1 J(1J)) K
B[Jun]= = J,
How large is K? The answer depends on the application domains. For example, for training large- scale machine learning models, it appears that K = 512 or K 1024 might be sufficient (Li et al., 2011). However, for approximate near neighbor search using many hash tables (Indyk & Motwani, 1998), it is likely that K might have to be much larger than 1024 (Shrivastava & Li, 2012; 2014).
In the early work of MinHash (Broder, 1997; Broder et al., 1997), actually only one permutation was used by storing the first K non-zero locations after the permutation. Later Li & Church (2005) proposed better estimators to improve the estimation accuracy. The major drawback of the original scheme that the hashed values did not form metric space (e.g., satisfying the triangle inequal- ity) and hence could not be used in many algorithns/applications. We believe this was the main reason why the original authors moved using K permutations (Broder et al., 1998).
1.2 OUTLINE OF MAIN RESULTS
From K Permutations two. The main idea of this work, is replace the independent per- mutations in MinHash with "circulant" permutations. Thus, we name the proposed framework C- MinHash (circulant MinHash). The "circulant" trick was used in the literature of random projec- tions. For example, Yu et al. (2017) showed that using circulant projections hurts the estimation accuracy, but not by too much when the data are sparse. In Section 3, we present some (perhaps surprising) theoretical findings that we just need 2 permutations in MinHash and the results (esti- mation variances) are even more accurate. Basically, with the initial permutation (denoted by a), randomly shuffle the data to break whatever structure which might exist in the original data, and then the second permutation (denoted by π) is applied and re-used K times to generate K hash values, via circulation. This method is called C-MinHash-(o, x). Before that, in Section 2, analyze a simpler variant C-MinHash-00, T) without initial permutation a. Although it is not our recommended method, our analysis for C-MinHash-(O.. π) provides the necessary preparation for later methods and the intuition to understand the need for the initial permutation.
From Two Permutations to one. In Section 5, we provide a more convenient variant, C-MinHash- (T, I), that only needs one permutation π for both pre-processing and hashing. Although the theo- retical analysis becomes very complicated, we are able explicitly write down the expectation of the estimator, which is no longer unbiased but the bias is extremely small and has essentially no im- pact on the estimation accuracy (mean square errors). Extensive experiments are provided verify that this variant has same estimation accuracy as (-MinHash- x) using two permutations.
In this paper, we mainly focus on presenting the fundamental idea of C-MinHash and the theoretical analysis on its uniform variance reduction with non-trivial efforts. Besides improving the Jaccard estimation accuracy when directly implemented in place of MinHash, the proposed C-MinHash mechanism can also be conveniently used as tool to improve more MinHash based algorithms, for example, the One Permutation Hashing (OPH, Li et al. (2012)). When combined with OPH, C- MinHash reduce the required permutation effectively 1/K permutation only. Since such combination is a research direction which requires independent introduction and efforts, we present the work in separate manuscript (which could be anonymously shared with Referees if needed).
2

---

Under review as a conference paper at ICLR 2022
Algorithm 2 C-MinHash-(0,,.
Input:
Binary data vector {0,1)?,
Permutation vector [D] - [D]
Output: Hash values h1 (x(())
For = to K
Shift и cireulantly rightwards by ls units: Th T
(b) m0 x2)
End For
2
D1
8
V
5
V8
1
V8
V2
Circular
V7
V3
1
V7
V3
8
Shift
V6
V
V6
V
1
V5
V5
7
π - (2, 1, 1,7,3,,,6
Th =
Figure 1: An illustration of the idea of C-MinHash. The data vector has three non-zeros, 02 01
0/ 1. this example, h1(v)= = 3, hx+1(v) =.
2 C-MINHASH-(4.. T) WITHOUT INITIAL PERMUTATION
As shown in Algorithm 2. the C-MinHash algorithm has similar operations as MinHash. The differ- ence lies in the permutations used in the hashing process. To generate each hash (g(v), we permute the data vector using -h which is the permutation shifted k units circulantly towards right based on æ. For example, = [3. 1, 2, 4), T = [4, 1, u = [2, 4.3, 1], etc. Conceptually, we may think of circulation as concatenating the first and last elements of vector to form circle; see Fig- ure We set the hash value b4 (v) as the position of the first non-zero after being permuted by m Analogously, we define the C-MinHash-(A. πT) estimator of the Jaccard similarity J(v, w)
1 Σ (h) hg(w)): K
Jo.n
where h is the hash value output by Algorithm In this paper, for simplicity, we assume K S D.
Next, we present the theoretical analysis for Algorithm 2, in terms of the expectation (mean) and the variance of the estimator Jo.r- Our results reveal that the estimation accuracy depends on the initial data distribution, which may lead to undesirable performance behaviors when real-world datasets exhibit various structures. On the other hand, while it is not our recommended method, the analysis serves a preparation (and insight) for the C-MinHash- т) which will soon be described.
First, introduce some notations and definitions. Given v, u E {0, define and f
1(v, a= Σ 1(0 = and w, 1}, f= 110 = w, 1}.
(5)
We say that (D,, w) is (D, (aa.f.a)-dlee a)-data pair, whose Jaccard similarity can also be written as J = f- Definition 2.1. Consider v, w {0, P. Define the location vector x E {0,x, with ar; being "O", "x", " "_", when 0; = w; = 1, v; + wn = and v; wn = O, respectively.
The location vector the hashes by (v) and hy (w) would collide if after permutation, the first "O" is placed before the first "x (counting from small large). This observation will be the key in our theoretical analysis.
fully characterize hash collision. When permutation T is applied,
3

---

Under review as a conference paper at ICLR 2022
Definition 2.2. For A, E (0,x,-), let {(A, ()) denote the set {(t.5) (x),
(A,B),j-iz -i- }.. For each 1 1 A v K define
(o( ((000)4), 41(4 {(0, ((0,x)); (2(4) ((0,
Go( = [(-))))( = [((, = x)): H2(A) [(x,- -))-
([(A)=([->>)
((--))
Remark 2.1. For the ease of notation, by circulation we write 2;j = - when D < j < 2D.
Definition 2.2 measures the relative location of different types of points in the location vector, for specific pair of data vectors, One can easily verify that for _ A - 1,
[ol + [ [C2] Col + Gol + [oo] a,
9n + 9 + [2 C2l + 92 + [22 = -
(6)
[oo + |H1 + [H2] |C.| |9 + [Hi] = a,
which is the intrinsic constraints on the size of above sets. We are now ready to analyze the expecta- tion and variance of Ju,n. It is easy to see that Ju., is still unbiased, i.c., E[Jo,r] J. by linearity of expectation. Lemma 2.1 provides an important quantity that leads to Var[Jo,-] as in Theorem 2.2.
Lemma 2.1. For any < S K with 1. D, have
E (1) = h. (w)) h,w) (o(\a) + (196(4)) ((())
f [ (4( where the sets are defined in Definition 2.2 and hg he are the hash values in Algorithm 2. Theorem 2.2. Under the same setling as in Lemma 2. the variance of Jo, is
J 2 ZΣR,
1)0K-++!
Var[Jo.z] = +
K
K2
where O & E. [A(h.(v) h.(w)) he [ww}]]] as Lemma 2.1 with any t A.
From Theorem 2.2, we see that the variance of Jo.r depends on a, f. and the size of sets L's and G's as in Definition 2.1, which is determined by the location vector æ. Since we use the original data vectors without randomly permuting the entries beforchand, Var[Jo,z] is called "location- dependent" as is dependent on the location of non-zero entries the original data.
C-MINHASH-(O,,4) WITH INDEPENDENT INITIAL PERMUTATION
Algorithm 3 (c,
Input: Binary data vector v E 13P,
Permutation vectors æ and a: [D] + [D]
Output: Hash values h1 (x,)...,,
Initial permutation: v' = (
For h = to K
Shift æ circulantly rightwards by & units: Ty = T
hx(v) min (1)
End For
The method C-MinHash--o, π) is summarized in Algorithm 3, which is very similar to Algorithm 2. This time, as pre-processing, we apply an initial permutation a L on the data to break whatever structures which might exist. Similarly, we define the C-MinHash- m) estimator of J as
1 Σ ((ha(v) ha (w)), K
ja
where fy 's are the hash values output by Algorithm We will present our detailed theoretical analysis and the main result (Theorem 3.5). First, by linearity of expectation and that and are independent, jo.r is still unbiased estimator E[J ] E[1 an immediate intuition, the following proposition emphasizes that the collision indicator variables in (7) are pairwise negatively correlated, which intuitively explains the source of variance reduction.
h,(w))] = J. To provide
4

---

Under review as a conference paper at ICLR 2022
Proposition 3.1. In (7), Cou((((((t) h((]]]((www))))))] ((h)())))))) hy(w)))) < 0, Vi #.
Proof. Denote & B (M((v) (1 hy(w))) for * j. The task is then to show that (o) = hi(w)), (())(())))))))))))))) = (((2))) E- J² < 0. By Theorem 3.5, Var [un) < Var(Jo,z), where VarlJMm J(ーJ = and
K E (())(()) = (hs(ww)))
27
Var[ TR ( [
)
- -²== K
J²
k=1
((1h))(() hi(w))l EEjf B|1 (h;(t) h4
h2(())} J²
K2
K²
J
K(K 1) (h,(w) = h,w))) (h5(w) hr(2))
- J²
where i j
K
K²
J.
(K -1EE
K J ((1J) - (8- (E- (1-
+
< 0 = -2
K
K
Next, we formally present the path to our main result. The next Theorem gives the variance of Ja. Theorem 3.2. Let a. f be defined as in (5). When a f (J & f0, 1}), we have
J (K -
Var[Jant
J2,
(8)
K
K
where with I = max(0, D - 22 + a), and
E = (mx
hh (h2 h,(w))]
E
lo
+
a(go 12)
f + 90 + 91
(f + gu + gz)f
12.12.90.913 D-5-1 (D-) (- (1)) (- (--0-)))--- (a)))) a-1 x Σ
(D-S-)))))
(--1
(9)
(D-e-1)
(D-1)
sml
The feasible set {lo, 12, to: 91 satisfies the intrinsic constraints (6), and
M1 = 90 - (D - f -8 -
112 = - f - 2--f 91:
n3 = 12 9o + D - f-s --91)), nu = 1, - (D - - g1).
Also, when or (J or J 1). we have V Var [a 0.
Since the original locational structure of the data is broken by the initial permutation o, Var[Jo,
only depends on the value of (D, a), i.e., it is Doccation-indepeneen
This would make the performance of C-MinHash- (a,, .) consistent in different tasks. Same as MinHash, Proposition 3.3 states that given 1 and f. the variance of Jo,s is symmetric about J = 0.5, as illustrated in Figure 2, which also shows that the variance of Jo. is smaller than the variance of the original MinHash.
Proposition 3.3 (Symmetry). Var Var[Ja,a] [Jo,z] is the same for the (D, f, -dta pair and the (D,5$ dd-aa pair, v0 S <asfsl D.
x
x10
5
MinHash
0.2
MinHash
0.8
2
0.2
Var Var(Je. Jax))
Var(Jox) JOs)
0.4
2
f/D
0.6
0.8
f/D
D = 1000
K = 500
1000
K
800
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
J
Figure 2: Var[Ja [Jom]] versus J, with D = 1000 and varying f. Left: K = 500. Right: K = 800.
5

---

Under review as a conference paper at ICLR 2022
109
102
fD=
J-066
Variance Ratio
Variance Ratio
D 1000
1D
10
0.3
10'
0.8
9:0
10
0.1.1
0.6
10.3
==
10
9.4
0.2
100
1D m 0.1
102
10
0.2
0.6
0.8
0.2
0.6
0.8
K/D
Figure 3: Left: Theoretical ε, f = 10. Each dash line represents the corresponding J². Mid:
Variance ratio Var[Jaru] D 1000, K 800. Right: Variance ratio Var[Jann] D 1000.
Var[Ja,r]
Var[Jo,a]
A rigorous comparison of Var[Ja,a] and Var[JMH] appears to be challenging task given the complicated combinatorial form of Var[Jo,r]. The following lemma characterizes an important property & (9), that is monotone in D when a and f are fixed, as illustrated in Figure (left). Lemma 3.4 (Increasing Increment). Assume f > a > are arbitrary and fixed. Denote En as in (9) in Theorem 3.2, with D treated as parameter. Then we have ED > &D for VD 2 f.
Equipped with Lemma 3.4, we arrive the following main theoretical result of this work, on the uniform variance reduction of C-MinHash-((a,m))
Theorem 3.5 (Uniform Superiority). For any two binary vectors v, w E 10, with J + 0 or 1, it holds that V Var [ w)] < V Var[J w)].
That is, using merely two permutations as C-MinHash- TT) improves the Jaccard estimation vari- ance of classical MinHash, in all cases. Next, in Figure 3 (mid) and Theorem 3.6. show that interestingly, the relative improvement is actually the same for any J, for given D, f and K.
Proposition 3.6 (Consistent Improvement). Suppose f is fixed. In terms of a, the variance ratio (orljhe(ve.w]] is constant for any 0 < a a (v.,))
How is the improvement affected by the sparsity (i.e., J) and the number of hashes K In Figure (right), we plot the variance ratio VariJscul Var[Ja.] with different f and K, given fixed D. We see that the improvement variance increases with K (more hashes) and f (more non-zero entries). Note that, by Proposition 3.6, here we do not need to consider which does not affect the variance ratio. The results in Figure 3 again verify Theorem 3.5, as the variance ratio always greater than
NUMERICAL EXPERIMENTS
In this section, we provide numerical experiments validate our theoretical findings and demon- strate that C-MinHash can indeed lead to smaller Jaccard estimation errors.
4.1 SANITY CHECK: SIMULATION STUDY
simulation study is conducted on synthetic data to verify the theoretical variances given by The- orem 2.2 and Theorem 3.2. We simulate D 128 dimensional binary vector pairs (v, w) with different / and a, which have special locational structure that the location vector x is such that "O"'s followed by (ʃ a) "x""'s and then followed by (D -) "_"'s sequentially. We plot the empirical and theoretical mean square eπrors (MSE = variance + bias?)
) in Figure 4:
The theoretical variance agrees with the empirical observation, as the curves overlap, con- firming Theorem 2.2 and Theorem 3.2. The variance reduction increases with larger K.
Var[Jo,z] (C-MinHash- r)) is always smaller than Var[JMH], stated by Theo- rem 3.5. In contrast, Var[Jo.z] (C-MinHash--0,,t x)) varies significantly depending on dif- ferent data structures, as mentioned in Section 2.

---

Under review as a conference paper at ICLR 2022
10"
109
Simulation
10"1
Simulation
Simulation
(0.n) Theory
(0.a) Theory
(0,r) Theary
1
(a.s) Theory
(r.at) Theory
10
((ox)) Theory
MSE
MinHash
MSE
MinHash
MSE
MinHash
10
10
10
(D.aa) (128,8.4)
(D...a)
(128,8,1)
10
(D,f,))
(128,8,2)
10
20
40
60
80
100
120
20
40
60
80
100
120
20
40
60
80
100
120
K
K
10
10"
109
Simulation
Simulation
(D.1.a) (128,128,16)
(0,=) Theory
(0.a) Theory
100
(a.x) Theory
10:2
(o.a) Theory
10
MSE
- MinHashh
MSE
MinHash
MSE
10.9
(D...a) = (128,6422)
10
10'4
(0.=) Theory
Simulation
(D.1.a)
(128,64,8)
(o.m) Theory
MinHash
10
10
10
20
40
100
120
40
60
100
120
40
60
80
100
120
K
Figure 4: Empirical vs. theoretical variance of Jo.- (C-MinHash- (0, 7)) and Jo.n (C-MinHash-
(a, m)), on synthetic binary data vector pairs with different data patterns.
10
10*
Moan Absoluta Erer
c.8
Moan Absolute Eror
rifash
Azsolute Error
Maethahh C-diihaat--BB.1
Moon Azsolule Eneer
CIFAR
0.8
BBC
C C-MMiiashh--..i
O Mintaadh--ooo lovd)
- ---HHH
Mirizsh- 00.
NIPS
Midlash
C-Wiiiodh le
10
11
10
2
K
Figure 5: Mean Absolute Error (MAE) of MinHash and C-MinHash on real-world datasets.
4.2 JACCARD ESTIMATION ON TEXT AND IMAGE DATASETS
We test C-MinHash on four datasets, including two text datasets: the NIPS full paper dataset from UCI repository (Dua & Graff, 2017), and the BBC News dataset (Greene & Cunningham, 2006), and two popular image datasets: the MNIST dataset (LeCun et al., 1998) with hand-written digits, and the CIFAR dataset (Krizhevsky, 2009) containing natural images. All the datasets are processed to be binary. For each dataset with n data vectors. there are in total n 1)/2 data vector pairs. We estimate the Jaccard similarities for all the pairs and report the mean absolute errors (MAE). The results are averaged over 10 independent repetitions, for each dataset, as shown in Figure 5:
The MAE of C-MinHash-(o, T) is consistently smaller than that of MinHash, again con- firming Theorem 3.5 the benefit of the improved variance. The improvements become more substantial with larger K, which is consistent with the trend in Figure 3.
Without the initial permutation a, the accuracy of C-MinHash- (0, .) is affected by the distribution of the original data, and it is worse than C-MinHash-(o, r) all these four datasets. Also, the performance of C-MinHash-(OO, x) on image data seems much worse than that text data, which we believe is because the image datasets contain more struc- tural patterns. This again suggests that the initial permutation o might be needed practice.
In summary, the simulation study has verified the correctness of our theoretical findings in Theo- rem 2.2 and Theorem 3.2. The experiments with Jaccard estimation on four datasets confirm that C-MinHash more accurate than the original MinHash. The initial permutation a recommended.
C-MINHASH- ::: PRACTICALLY REDUCING TO ONE PERMUTATION
We propose a more convenient variant, C-MinHash- π), which only requires one permutation. That is, π is used for both pre- pre-procsssing and circulant hashing. The procedure is the same as Al- gorithm except that the initial permutation is replaced by Denote the Jaccard estimator jr.r-
7

---

Under review as a conference paper at ICLR 2022
The complicated dependency between (initial permutation) and T-ok (hashing) makes the theoret- ical analysis challenging. In the following, we provide the mean of each hash collision indicator.
Theorem 5.1. Assume K S and let a. f be defined as (5). The location vector defined in Desinition 2. Denote B1 = {i æ; 0}, B2 {i = x} and B3 {i = ---. For
a S S D and S k S K, define
A (1x (i (i+ - mod +){1s A+ 120 (i h - mod D) + +1>11 5}-
Let n 1- (1) = 1=:==000- = =0: DOi (-)ه be the number of "O" points in A-)) Analogously let n- (0=2()),0 nn,)n be the number of "x" and "" points A-()), and n+.1 a4 2(),,, a+ be the number of "O", "x" and "-" points in A+()). Then, for the k-th C-MinHash-CC (T, x) hash,
B[1(ba(v) ha(w))] - ΣE Pz(Z) - j=1 2EB,
{Σ v+(I++
Σa-=ip PIJ.
2-,1 11,
TEB
where P2(Z) is the density function of Z (2_,611 x+, which follows hyper( D, D ((, with domain Oj For 1, denote 1 1 *h E By and
12(1) = Σ
Σ
# p
p-p n (5)
+ llq = (2
z-
1))
z+g PoJJ
n (i)
nt.q(i)
iEBoui p=l
Σ
1$ (1
2- )11
2-19
+ Σ
1# p
(1
2-g9 )11
2- 1]
PaJ
4
.- -
n- n2
iEB
pfq
where 1" = (i+ mod D) + i# = (i - k - mod D) + 1, Vi. Define J = a-11
8- and
(1) j-bb
( (1-1)
(D-j-ho)
P₂ P.
(rg 11-1--11
P3
ritrz
1i + T2 (D-))
(D-1)
T3
(ritta)
r3
J n1 11 11 1}
11 + 12
1 7 3)
(1
) q 1,2,3,
j-j D-j- bo
D bn
where b0 = >x_ 2 Ti- = a- 24, 122
/ a- 2- 24,2 and r3 = D-
Theorem 5.1 says that E[1 (b)( = hy (w)) would different for different k. Figure 6 presents numerical examples to validate the theory and demonstrate the magnitude of bias (recall MSE- bias? + variance), where the simulations match perfectly Theorem 5. As the bias EII (hx(w) =
x10
x10
Simulation
Simulation
Simulation
Theory
Theory
Theary
2
Blas
Blas"
3
Blas?
(64,32,16)
(64,4,1)
2
(64
0.5
0
K
K
0.26
0.51
0.51
Simulation
(D.f,a) = (64,4,1)
Simuletion -Theory True
Simulation -Thoory True
Mean Estimate
0.255
True
Theory
Mean Estimate
0.505
Mean Estimate
0.505
0.25
0.5
0.5
0.245
0.495
0.495
(64,4,2)
(64,32,16
20
40
60
20
40
k
Figure 6: 1st row: b (B[J J)² vs. number of hashes K on simulated (D. f. data
pairs, D = 64. 2nd row: mean of each collision indicator.
8

---

Under review as a conference paper at ICLR 2022
he (w))] can be positive negative, the overall bias of Jn, would approach 0 as K increases. From the 2nd row, we see that bias is very small (10-3 or even smaller) and indeed converges to 0 with more hashes, i.e., the averaging effect. Also, from the proof (see Appendix A.8) we can know that when a and f are fixed, as D increases, [[Ja,s] would converge to J.
We found through extensive numerical experiments that, the MSE of Ja is essentially the same as Ja.r. Figure 7 (Ist row) compares the empirical of C-MinHash- x) with the theoretical vari- ances of C-MinHash-(a,, x), where the simulated data has the same special locational structure as in Section 4.1. In the 2nd row, present the MAE comparison the curves for these two estimators (Ja.. and J match well. In all figures, the overlapping MSE curves verify our claim that we just need one permutation π. Due to the space limitation, we provide more empirical justifications in Appendix B.
real datasets, where see that
100
10
10
Parm
Parm
Parm
2 Porm Thoo,
2 Pom Theo
- Por Theo.
(128,128,16)
20
MSE
MSE
MSE
MSF
10
10
10-3
10
(1 (128,64,8)
10
(128,8.2)
10-9
10
Theo.
100
10"
10P
102
10
10
100
101
10
10
10'
1OR
K
K
x100
x
10'
10"
Moan Absoluta Entrr
2 Phrm Pem
Mean Aosolute Error
Perm
Parm
Moan Assolute Eror
Parm
Absokute
BBC
NIPS
MNIST
10
2
210
2/2
2²
K
Figure 7: 1st row: estimator MSE vs. K on simulated data pairs. 2nd row: MAE of Jaccard estimation on four datasets. "1 Perm" is C-MinHash- (TT, x), and "2 Perm" is C-MinHash- r).
6 CONCLUSION
The method of minwise hashing (MinHash), from the seminal works of Broder and his colleagues, has become standard industrial practice. One fundamental reason for its wide applicability is that the binary (0/1) diggendimeniinnll representation is convenient and suitable for a wide range of practical scenarios. The so-called Jaccard similarity is a popular measure of similarity in binary data.
To estimate the Jaccard similarity J, standard MinHash requires to use K independent permuta- tions, where K, the number of hashes, can be several hundreds or even thousands in practice. In this paper, we proposed Circulant MinHash (C-MinHash) present the surprising theoretical results that, with merely 2 permutations, we still obtain an unbiased estimate of the Jaccard similarity with the variance strictly smaller than that of the original MinHash, as confirmed by numerical experiments on simulated and real datasets. The initial permutation is applied to break whatever structure the original data may exhibit. The second permutation is re-used K times in circulant shifting fash- ion. Moreover, we analyze a more convenient C-MinHash variance which uses only I permutation for both pre- peeprccessing and circulant hashing. We derive the complicated mean estimation, and validate through extensive experiments that it has the same Jaccard estimation accuracy as using 2 permutations with strict theoretical guarantee.
Practically speaking, our theoretical results may reveal a useful direction for designing hashing methods. For example, in many applications, using permutation vectors of length (e-g..) 230 might be sufficient. While it is perhaps unrcalistic store (c.g..) K 1024 such permutation vectors in the memory, one can afford to store two such permutations (even in GPU memory). Using perfectly random permutations in lieu of approximate permutations would simplify the design and analysis of randomized algorithms and ensure that the practical performance strictly matches the theory.
Finally, mention that work can be used as building block to improve Li al. (2012), reducing the required one permutation to effectively 1/K permutation only. If needed, we would be happy anonymously share the technical manuscript with the related results.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Michael Bendersky and W. Bruce Croft. Finding text reuse on the web. In Proceedings of the Second International Conference on Web Search and Web Data Mining (WSDM), pp. 262-271, Barcelona, Spain, 2009.
Andrei Z. Broder. On the resemblance and containment of documents. In Proceedings of the Con- ference on Compression and Complexity of SEQUENCES, pp. 21-29, Positano, Amalfitan Coast, Salerno, Italy, 1997.
Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, and Geoffrey Zweig. Syntactic clustering of the web. Comput. Networks, 29(8- 13): 19911117-1166 1997.
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. Min-wise inde- pendent permutations. In Proceedings of the Thirtieth Annual ACM Symposium the Theory of Computing (STOC). pp. 327-336, Dallas, TX, 1998.
Gregory Buehrer and Kumar Chellapilla. A scalable pattern mining approach to web graph com- pression with communities. In Proceedings of the International Conference on Web Search and Web Data Mining (WSDM), pp. 95-106, Stanford, CA, 2008.
Moses S. Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC), pp. 380-388, Montreal, Canada, 2002.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael Mitzenmacher, Alessandro Panconesi, and Prabhakar Raghavan. On compressing social networks. In Proceedings of the 15th ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), pp. 219-228, Paris, France, 2009.
Ondrej Chum and Jiri Matas. Fast computation of min-hash signatures for image collections. In Proceedings of the 2012 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 3077-3084, Providence, RI, 2012.
Abhinandan Das, Mayur Datar, Ashutosh Garg, and Shyamsundar Rajaram. Google news per- sonalization: scalable online collaborative filtering. In Proceedings of the 16th International Conference on World Wide Web (WWW), pp. 27 1-200, Banff, Alberta, Canada, 2007.
Fan Deng, Stefan Siersdorfer, and Sergej Zerr. Efficient jaccard-based diversity analysis of large document collections. Proceedings of the 21st ACM International Conference on Information and Knowledge Management (CIKM), pp. 1402-1411, Maui, HI, 2012.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:://aarchii ics uci edu/ml.
Dennis Fetterly, Mark Manasse, Mare Najork, and Janet L. Wiener. A large-scale study of the evolution of web pages. In Proceedings of the Twelfth International World Wide Web Conference (WWW), pp. 669-678, Budapest, Hungary, 2003.
Derek Greene and Padraig Cunningham. Practical solutions to the problem of diagonal dominance in kernel document clustering. In Proceedings of the Twenty-Third International Conference on Machine Learning (ICML), pp. 377-384, Pittsburgh, PA, 2006.
Kaiming He, Fang Wen, and Jian Sun. K-means hashing: An Eefinity-preservve quantization method for learning binary compact codes. In Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2938-2945, Portland, OR, 2013.
Monika Rauch Henzinger. Finding near-duplicate web pages: large-scale evaluation of algorithms. In Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Devel- opment in Information Retrieval (SIGIR), pp. 184-291, Seattle, WA, 2006.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC), pp. 604 613, Dallas, TX, 1998.
10

---

Under review as a conference paper at ICLR 2022
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86( 86(11):22785) (22172227222,2, 1998.
David C. Lee, Qifa Ke, and Michael Isard. Partition min-hase for partial duplicate image discovery. In Proceedings of the 11th European Conference on Computer Vision (ECCV), Part I, pp. 648- 662, Heraklion, Crete, Greece, 2010.
Ping Li and Kenneth Ward Church. Using sketches to estimate associations. In Proceedings of the Conference on Human Language Technology and the Conference on Empirical Methods in Natural Language Processing (HLI/EMNLP)) pp. 708-715, Vancouver, Canada, 2005.
Ping Li and Amd Christian König. Theory and applications of b-bit minwise hashing. Commun. ACM, 54(8):101-10,, 2011.
Ping Li, Anshumali Shrivastava, Joshua Moore, and Arnd Christian König. Hashing algorithms for large-scale learning. In Advances in Neural Information Processing Systems (NIPS), pp. 2672- 2680, Granada, Spain, 2011.
Ping Li, Art B Owen, and Cun-Hui Zhang. One permutation hashing. In Advances in Neural Information Processing Systems (NIPS), pp. 3122-3130, Lake Tahoe, NV, 2012.
Anshumali Shrivastava and Ping Li. Fast near neighbor search in high-dimensional binary data. In Proceedings the European Conference on Machine Learning and Knowledge Discovery in Databases (ECML-PKDD), pp. 474-489, Bristol, UK, 2012.
Anshumali Shrivastava and Ping Li. In defense of minhash over simhash. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 886- 894, Reykjavik, Iceland, 2014.
Acar Tamersoy, Kevin A. Roundy, and Duen Horng Chau. Guilt by association: large scale malware detection by mining file-relation graphs. In Proceedings of the 20th ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), pp. 1524-1533, New York, NY,
2014.
Felix X. Yu, Aditya Bhaskara, Sanjiv Kumar, Yunchao Gong, and Shih-Fu Chang. On binary em- bedding using circulant matrices. Mach. Learn. Res., 18:15001-150:00, 2017.
Juan Zamora, Marcelo Mendoza, and Héctor Allende, Hashing based clustering in high dimensional data. Expert Syst. Appl., 62:202-2222 2016.

---

Under review as a conference paper at ICLR 2022
A PROOFS OF TECHNICAL RESULTS
Notations. In our analysis, we will use I, to denote ((hx(v) - (w)) } in for v1 2 < K, where h is the hash value. Given two data vectors U, w E {0, 13 Recall in (5): = Σis1 1(u; = I and w; 1], ʃ E [0; or w; = 13. Thus, the Jaccard similarity J a/ʃ. We also define J= (a 10111/111))
Definition A.1. Let v, w E [0, Define the location vector as x E [0,,,--0, with æ; being "O", "x", "-"when Vi Wi 1, U2
and v; w; O. respectively.
Definition A.2. For A,B 10,x, x -) let {(1,5) (A, denote a pair of indices {(i.
(0), 05) = (A, -- AJ. Define
(o(A) =((i,)) (0,0))A,, (i(
9i(A)= ((..)) ,9((A)= = (O,,))(O,-))))
(2(1) (0,x));
Go(4) -
(o( [(i,)): (x. Hi(A) (x,,,)):x,x)]]); H2(A) = (xx,)))(x:+)))
Remark A.1. For the ease of notation, by circulation we write zj = Dj-D when <js< 2D.
One can easily verify that given fixed a, f, D. it holds that for V1 S A S K 1,
[c((4)] + (4)) + [2)( = [م,( + ( + [Hn( =
[Go(4)] + (4) + [4, | [92(4) [122(A) = - S,
(10)
(A)( + [A]( + [H2(A)] = [4)( + [ + [Hi(A)] 5 a.
We will refer this as the intrinsic constraints on the size of above sets.
A.1 PROOF OF LEMMA 2.1
Lemma 2.1. For any & s <t K with t = A, we have
Eg (h, = h, (())) [u(w))]] [o((D) (19o( (C2())D
f + (4)
(9)
where the sets are defined in Definition 2.2 and hg, he are the hash values as in Algorithm 2.
Proof. To check whether a hash sample generated by MinHash collides (under some permutation T). it suffices to look at the permuted location vector æ. If collision happens, after permuted by n type "O" point must appear before the first "x" point. That said, the minimal permutation index of "O" elements must be smaller than that of "x" elements. If the hash sample does not collide, then the first "x" must appear before the first "0" Note that "_" points does not affect the collision.
To compute the variance of the estimator, it suffices to compute E[1,1,] Let L, g and H be the union of L's, G's and H's, s, respectively. In the following, we say that an index belongs to set if is the first term of an element in that set. We have
( a, | |
|
D
One key observation that, for a pair j) in above sets, the hash index (i(()) will be the hash index of nt (T). We begin by decomposing the expectation into
E[1,1,] = Picollision s, collision t]
Σ
Picollision s at E collision i]
GEC
Σ CEC
Picollision at i collision t).
(11)
where i is the location of the original "O" in vector x that collides for s-th hash sample. It is different from the exact location of collision in xT(T)). Note that the permutation is totally random, so the location of collision is independent 1,, and uniformly distributed among all type "O" pairs.
12

---

Under review as a conference paper at ICLR 2022
1) When 1 Ly. In this case, the minimum index of the type "O" pair in x(TT), Ty (i.), is shifted to another type "O" pair in z(T.). Therefore, the indices of pairs with the first element being "O" or "x" originally in 20 (TTT)) will still be greater than n (32). If sample collides at i hash sample t will collide when
1. All the points in G1, after permutation æ.. is greater than ny (X)). In this case, regardless of the permuted Gu, hash t will always collide.
2. There exist points in 91 after permutation я, smaller than ny (Xg), and also points in 90 that is smaller than the minimum of permuted G1.
Consequently, we have for i E Lo.
Picollision at e collision
(()) (1). Vi H HULLEE and min IT (T) > T. ((,)) JEC:
+ P T&
< n. (1), E HU L/E and min (f( < min xz xx())))
JE9o
jE9,
1901
19
f+ 191
f+ 190 + 191
+ 19
100 19
[ +
(12)
( Gol (9)((( + (91l){
This probability holds for vig Co.
2) When i E L1. Similarly, we consider the condition where ig E L1, and both hash samples collide. In this case, (it) would be shifted to "x" pair in z(T)). That is, the indices of pairs with the first element being "O" or "x" originally in (TT,) will all become greater than n. (i)),, which now is the location of "x" pair x(T,). Thus, to make hash t collide, we will need:
At least one point from Go is smaller than any other points in H U CUG1 after permutation Tg.
Therefore, for any 1 E L1.
Picollision 8 at i collision t)
P(TT(13 n. (i), HU and min Tz(s) < min(m.(i)). min n. (j)
JE9c
jE9,
1Gol
a
1
f 1901
191
f
Gol
(13)
( Gul + (rl)
which is true for Vic E C1.
3) When i Cz.
In this scenario, i. (Vt) would be shifted to a "-" pair in x(T)). Therefore, if hash collides, hash t will also collide when:
After applying n., the minimum of Lo U Ho U Go is smaller than the minimum of L1 U Hi UG,.
Thus, we obtain that for any i E L2,
Picollision s at i collision t] P[m, (it) (1(1), HUC/E and
min jECoUS
Tz(1)
min jEL,USIHH
Te(i)l
A P[Ω].
13

---

Under review as a conference paper at ICLR 2022
Let 1,,;; denote the event {T² (i))). C/ig). Then Ω can be separated into the following several cases:
1. Ω1 Lay miosE TT(i) < minjec,um, me(i), and minjec,ux To(i) minjeg, m²()).
2. Ω2: Ia minjecouHo Tz(i) < minjec,uah *s(),, and minjecouRe =z(i) >
minjec ms(s) > minjeso ms( (t))
3. Ω3: 1.. min T.()) < minjec.uu, me(), and minjecoum, Tz(i)
minjeg, m=(i) > (1())) > minjeg, Te()).
4. Ωs: layg, Co (j) < minjecium To(i), and minjec,umo To > T TT(())
minjea, m=(s) > minjeco (i).
5. Ωz: 1852, minjec, (j) > minjec,um, (i),,, and (()) < minsego mz(i) <
minjEc,uH,,g,, ()))).
6. Ωg: La.g min (j) minjec,um, To (i), and minjeg. nz(i) Te(it) < minJEC,UU,,u. ())...
We can compute the probability of each event
1
Col + |Hol
P[R)]
a
1 91
Col
Hu
L1
H1
191
a 1901
(
Go (S + (1l)'
P[[ =
1
a
19ol
f + 1ul + 19
Gol + 19
+ [Col + |Hu]
+ |41 + [7g]
[91
[Col + |7
Coll
+ Hoo
+ |,C|| + [7||| + |
Col +
Hol + |211 + HH4
|Co|
a - Gol
f + |Gol + 1911
f f - 1lol
f f- 190 1
|Gol
|911 (a 19o1)
(f + Gol
+ () - (f Goo - 1))))
19o1
1
191
[Co 1H4
P[[a]
f + 19ll
+ 1911
f + 11 Lul + 176l + +1 + 174 + 91
Cul + 774 + 44 + 1761
|00| |91
(a (9o1)
(f Gol
+ (f
+ (91(((f
(f - | - 19
19o1
|
1Col + |Hal
P[[4]
f+ 19ll
+ 1
f + 1
Lol + |H41 + |611 + 1741
|Gol |6 (a- ())
( Gul
(/ + (
|Col - -1
1
|Gol
C1 + |7
P[[s]
f + Gol
9i Go |9
1Co + |HHo + C1 HH
Col
HHo] 12, + |71
1col
(ʃ - a - |
if + Gol
1l - Gool
1Gol
[C + 174,
P[Sa|]
f+ Gol
+ |il ] Col + Hol + |2il + HH
|Gol (f - a - 1)
(f + Gol
+ (f - 19ol - 1(
14

---

Under review as a conference paper at ICLR 2022
Note that
P[22] + P[03] + P[Ω.]
Gol |91| (a (ol)
1
(J'+ 9ol [9 [oo - [9 [f | + (Go)) + (gil)
J(S + 9
|oo 1911 (a- (3) -
[90] + (91l)
( Gol [9 - |oo | (ol)(s + [Gil)"
Summing up all the terms together, obtain P[[]]
P( f(f + Goo + (91)(ff 1 - 191--11100 (a (1-1)iaa1110000 (Gol) | 19 19ol (91
( 190 + (1 [90] - // (6 (9))s
2f - (
+ (f + |9 + (9
(a (f [9o] [] - +
(91 (o) + 19.
+f+ + 195 + (9 - - - ( -
- -fol) + +l
(a (f - 1
(f -
(f + 190l + 19 (f [ol - (f (96)) + 19)))
+ 19ol
(14)
(f + 1ull + (2l)s
which holds for Vig L2. Now combining (13), (14) with (11), obtain
1Cul
GollC|1ICol
Guul L1
(a + (9
B[1.1d
f+ 19
(f Gol + (l + 19)l) (f + Gol +
Gil)
(f Gol + G Gilf
(15)
Here, recall that the sets associated with all 1 1 < K such that A L - Using the intrinsic constraints (10), after some calculation we can simplify (15) as
CCol
a a( + [2l)
Ex [1,1e]
f Go
19
(f + Go 1
which completes the proof.
A.2 PROOF OF THBOREM 2.2
Theorem 2.2. Under the same setting as in Lemina 2.1, the variance of Jo,x is
Var[Jo.z] = K + 2Σ
J
1)0 x-+1 -+1
J2
K22
where O & E, [1(h<(v) = h.(w)) = h4 [w))}} as in Lemma 2.1 with any t - s = A.
Proof. By the expansion of variance formula, since E[[2]] = BE[1]] J, we have
Var [or J ==
K
K Lif
E
J²
(16)
K
K2
Note here that for VL. > the 1-th hash sample uses ne as the permutation, which is shifted right- wards by s from T.. Thus, we have B[1,1,] = E[4,-1i-d) for VD < i < s t, which implies E,1, 4.] = E[ (1 Vs < t. Since by assumption K < D, we have
K
K
E[1.1 = 2E (1 1 + 11 + (1213 + + +12 ... + IK-1
1 111k) (1,12 +1 1,12]
15

---

Under review as a conference paper at ICLR 2022
K
2
Σ
1)
1 1l
x-24
4=2
K
A
2
(8
K+1-
(17)
#=2
Finally, integrating (16), (17) and Lemma 2.1 completes the proof.
A.3 PROOF OF THEOREM 3.2
Theorem 3.2. Let a, f be defined as in (5). When a DJ {0, 1}}, we have
J
(K - -
Var Var[Sa,
J2
(18)
K
K
where with ( = max(0, D 2f + a), and
E = Σ
lu
a(9o + 12)
+
f
90 + 91
(f+ + 90 + g
10.12.80.81
D-5-1
D-
(--1--11 ( (D-f-a)
Σ
n3
a-11
-12
D-c D-a-1
D-1)
(19)
The feasible set {lu, 12, 90 90:919 91) satisfies the intrinsic constraints (6), and
ni 90 (D f -999), 112 = D -
91:
ng = 12 9o + (D - s g1), n1 = 1 - (D - - -91).
Also, when or (J
J = 1), we have Var [Ja,z] 0.
Proof. Similar to the proof of Theorem 2.2, we denote O = E,, [1.1]] with |t - s = A. Note that now the expectation is taken w.r.t. both two independent permutations o and Since o is random, we know that θ = O₂ = x-- Then by the variance formula, we have
J² K
(K (K-1)0, J²
Var[Ja.=]
(20)
K
Hence, it suffices consider O₁ In this proof, we will set A = and drop the notation A for conciseness, and denote ε = O from now on. First, we note that Lemma 2.1 gives the desired quantity conditional on a. By the law of total probability, we have
Col
a( (C2)
= E.
+ (f+ 1S + 1
(21)
f
+
where the sizes of sets random depending the initial permutation (i.e. counted after permuting by a). As a result, the problem turns into deriving the distribution of 141, [42), Go and [9 under random permutation a, and then taking expectation of (21) with respect to this additional randomness.
When a = 0, we know that Lno = [22 = |col = 0, hence the expectation is trivially 0. Thus, the Var[Ja,n = O. When / = |9 0, and the constraint the sets becomes
Col + |ool = Coo + C2 = f. C2 |Ga Gol
+ G2l D -
Then (21) becomes
C
Gol + L2
ē= E
Gol
f + Gol
16

---

Under review as a conference paper at ICLR 2022
[Co + Gol + |C2l
Es
=
++ |90|
Therefore, when f = a, we also have Var[Jann] = O.
Next, we will consider the general case where 0 < < D. This can be considered as a combinatorial problem where we randomly arrange type "O", (f-a) a) type "x" and (D - type "_ " points in a circle. We are interested in the distribution of the number of [0,0}. f0, x [O,-), {- and {-,x) pairs of consecutive points in clockwise direction. We consider this procedure in two steps, where we first place "x" and "_" points, and then place "O" points.
Step 1. Randomly place "x" and s_" points on the circle.
In this step, four types of pairs may appear: {-, (-, {x, x} and (x,-) Denote Ci, C2. C3 and C4 as the collections of above pairs. Since
C1 C4 |G1 [C2| D f, C2 + Ca = [C2] + |Ca|= f
knowing the size of one set gives information on the size of all the sets. Thus, we can characterize the joint distribution by analyzing the distribution of Ct First, placing f) "-" points on a circle leads to (D-f) f) number of {-. -} pairs. This (D-f) elements can be regarded as the borders that split the cirele into (D- - f) bins. Now, we randomly throw (f- a) number of "x" points into these bins. If at least one "x" falls into one bin, then the number of {- -} pairs ([G2)) would reduce by 1, while |C2] and |Ca| would increase by 1. If = "x" points fall into one bin, then the number of {x, x) ((Cg)) would increase by (z 1). Notice that since S D and D - f
we
have max(0, D 2f + a) S 8 5 D
Consequently, for this range, we have
P P(GI = 8) = P |11 = Csl = a (D - 5)
( ,)
f-a-1
D-1--11)
(1-0-1)
D-f-11
f-a-1
1-8-11
(22)
D-a-1)
D-1--1
The second line is due to the stars and bars problem that the number of ways to place n unlabeled balls in m distinct bins such that each bin has least one ball is (==1)- For [Ca| 8, we need s. Moreover, the number of ways to m- 1 ). When counting the total number of possibilities, we
n = f - a (number of "x") and m = C2l = D
place n balls in m distinct bins is (-+
have n = - and m - f. This gives the denominator. We notice that (22) is actually a hyper-geometric distribution.
Step Randomly place "O" points on the circle.
We have the probability mass function
P[y] 2 P(1C
|6 41 L2l = l2, Gol = 90. 99.1911 = 91
D- D-1-1
P(|cil= Σ
41 |C2 = l2, Goo go. 191l 91 silica = =[(Gli=== (23)
DD22tt+
Now it remains to compute the distribution conditional on C1 Here we drop Lol because it is intrinsically determined by [C,] and [C2]. Again, given a placement of all "x" and "_" points, each consecutive pair can be regarded
distinct bin. Therefore, now the problem is to randomly throw a type "O" points into that (D- a) bins, given that we have placed type "x" and "_" "ponnts on the circle with C1l determined correspondingly). i i= 1,2,3, 4, make the event v happen. Note that
(and thus |C2 = C2 D -
and |Cal = - a (D f- s) are also the following, we count the number of "O" points that fall in C,
17

---

Under review as a conference paper at ICLR 2022
When at least one "O" point falls into C1 (between {-, --, [C2l and [go] increase by 1.
When at least one "O" point falls into C2 (between while | decreases by L.
{-, x}), |Ci] and |Go] increase by 1,
When at least one "O" point falls into C3 (between (x, 142 increases by 1.
When at least one "0" point falls into C₁ (between {x, x x)), [4]] increases by 1.
We denote the number of bins in C, i = 3, 4 that contain at least one "O" point as ni, 722 R3,, 14, respectively. As result above reasoning, in the event V, we have
71 + 12 = 12
n2 114 1
n1 n2 90.-
D f - 112 = 91
Solving the equations gives
11 (D - f- - 91),
n2 D - 91,
n3 1 90 + (D f 91);
n4 = 4 (D f - $ 91).
Note that i= 04 = 1 + l2. Therefore, event Ti equivalent to randomly pick n1, f2, ny and n4 bins in C1,...Ca. and then distribute type "O" points in these (41 + 12) bins such that each bin contains at least one "O", Hence, we obtain
(i, (
D-1-8 (D-1-s) 1D-1 n2
(1 a-1 (144-11
P[1GI = h, 1,2l = 12, Gol go: |9 = gi |C1| = 8f
n3
D-1
(-a-1
(() D--
10-f-9) f
(D--(DDf-))) a-1
11
ng
n4
l-11-1
DD11)
(24)
which is also multi-variate hyper-geometric distributed. Now combining (22), (23) and (24),
obtain the joint distribution of Lal, [, L2), |So| and |91| as
P(GG11 = h, 12l = 12, Gol
go. |91 91
D-5-1
D- (D DD-1- f-) (1-a aa-a-(D-- -D-------)) (0-9--1))
(D-Ta-1)
Σ
(25)
(D-1)
(----1)
s= 2f+a)
Now let E be the feasible set of (lo, 4, go 91 92) that satisfies the intrinsic constraints (10). The desired expectation w.r.t. both π and a can thus be written as
lo
aggo + 12)
E
+
f 9o +
+f + 991ff/
D-1-1
(-)--110) (P- (D-1-0) ( (-a--(D-f-s) (----1))
( f- f-a-1
Σ
n2 as
14
D-1-8-1)
D-1
w-a-1
== D=-nxx(ODD22+al) 2f)+a
D-
The desired result can then follows by (20).
A.4 PROOF OF PROPOSITION 3.3
Proposition 3.3 (Symmetry). Var jor]Jax is the same for the (D, f. a) pair and the (D, dd-aa pair; v0 < D.
18

---

Under review as a conference paper at ICLR 2022
Proof. For fixed a, f. D, let E be the expectation defined in Theorem 3.2 for (v1, w1), and Eg be that for (V2, W2). From Theorem 3.2 we know that
to
a(go + 12)
b2. f + 91
+ (ʃ + 90 + 91)
where (lo, 12, yo, (0,99) 91) follows the distribution of (ICo), [C2, (o (9il) associated with the location vector 21 of (V1, U2). For data pair (22, W2), we can consider its location vector 22 as swapping the "O" and "x" entries of æ1. Now denote the size of the corresponding sets (Definition 2.2) of 02 as V,s, g(s,, his,, for i 0, 1, Since is applicd before hashing, by symmetry there is a one-to-one correspondence between the location vectors. More specifically, l corresponds to hi, &o corresponds to 91. 9í corresponds to 9o, and 1/2 corresponds to h2. Therefore, in probability can write
1 f 96 + 9 (f 96 + +
alg6 + 12)
hn
a)-a)(9 + h2)
E (hn.
f 90 +
(f 90 + gn)f
Consequently, we have
h a(go + 12) (f a9 h22
ε, E = A1
Eg
f + 91
(f 90 + 91)f
In the sequel, the subseript expectation is suppressed for conciseness. Exploiting the constraints (10), deduce that h (f a. 4 91, h2 lo gu 11 + 91 and lo + 4 12-
Using these facts we obtain
(1o
(f - a) + + 9f + a(go + 12) - (f (4o + 90 + 4 + 2g a)
- E2 E
( + 91)S
(2a
1 + - 12). + a(go 12) - (J (2 + 90 12)
(f + + 91)
2(f 90 -11a (f 90 f
E
(ʃ g0 9.)
2J
Comparing the variances of Jo (U1, and Ja (V2, W2), derive
Var[Jo, (V1, wi)] - Var [Ja, (V2, W2)l
J (K 11) (2)
1-
+ (K 1)82
(1 J)
K
K
K
K
K -
K -
(2J 1) 1)+
{ E2)
K
K
This completes the proof.
A.5 PROOF OF LEMMA 3.4
Lemma 3.4 (Increasing Increment). Assume a > and f >> a are arbitrary and fixed. Denote ED as in (19) in Theorem 3.2, with treated as a parameter. Then we have ED41 > for f.
Proof. Let the probability mass function (25) with f and dimension D be Pa.f. 12, Io. 91)- Conditional on lo, 12.90.00 91 with elements, the possible values 1y 12 96- 9' when adding a " are
s6 9o + 1,4 = 4. 12,9 91 This is true when the new elements falls between pair of (x, (x, with probability 11+1g-0
19

---

Under review as a conference paper at ICLR 2022
s' 91 1,4 10.12 12.96 9o. when the new elements falls between pair of (x, with probability 1-a-ti-
o 91 + 1,1/2 = 112 - 1, 10 lu 96 go. when the new elements falls between a pair of (0, x). with probability
B.
1/ = 11 1.1/2 12 + 1. 9 90 + 1. 1. = 91, when the new elements falls between a pair of (), with probability 18-
All values unchanged, when the falls between other types of pairs, with probability D to
Denote En as the feasible set satisfying (10) with dimension D 2 S. Above reasoning builds correspondence between En and En More precisely, we have
1/
a(96 122 (f + gi)f
ED+1
Σ ED11
+
Pa. 96-
f
+
+ 9i
lo
a(3o + 1/ + 1)
4 + - 90 Pa.,.Dllo, 91)
90 91 +1
(f + 90 + 91 + 1)f
D
lo
a(go 12)
f f-a- a
a--4-- -91
Pa,, 91)
f + 9u + 91 +
9 1)f
D
lo
a(g0+1221
11
gf+ Po. 12. 90.
f + 90 + 91 + 1
lu 1
a(90+122
Lu
P
(l. 90.9))
f 90 91 +1
(ʃ + 90 + 91 + 1)f
D)
a(go (2)
D
f
go 91 Pa Pa. 12.0999
f + gu
+ 91
(f 90 g1)f
D
The increment can be computed as
3D A ED+1 - EED
ΣΣ
90-
40
4
a(go + + 1)
a(go + (2) f 9o + gi
D
f + 90 + 91 +1
f 90 + 91
+ 90 91 +1
Ep
1o
a(f a
91) alg
Po Po. 12. 91)
9
Df(f + 90 + 91 1)
( 90
12) f1o] a)- a(s 11 91)
Pa Pa.s.plb. (2..po(lo.2290..00
Df(f +00+++++++++++++++++++++++++++++
Df(f + 9u + + +1)
ED
2a + 2f)) 20(f a)(go + 91)
Pl.s.
DSU + +0 +
+ 1)
En
2a +
- -2) 2 2all-20(faaapp + +9)
E
Df +f 9 91 11
2f - -a- -hh))- -2) - a)44 - 2a a) + 91 + f
R
Df + 90 + 9f)(f + 90 + 91 + 1)
An(J - a)
2ah + + - a)lo
2a( - a)
E
E
E
D(f 90 (f 90 91 1)
D(f + gu + g1)(f 9u + 91 1)
Df(ff 90 91 1)
A 40(f - -) 2aEE 2( a) Eg 22(s a)
(26)
where
1
h1
Eo = E
Ei =
D(S + go + + + 90 +
D(S go g) + go +
20

---

Under review as a conference paper at ICLR 2022
10
92
E2 - LDJ + 90 + 9) + 90 + 91 1)
Es
D(S
DJU 90 + 91 + 1)
Note that here the expectations are taken w.r.t. the set size distribution with a, f. D. We can expand the terms of density function (25) to derive
Pa. (lu, 22 9u. 91)
D D-f-1
-D - a 1)!
Σ
DD (f+ 9o + +11 (1)]((((f + + +11 s||gi f-
(a-1))
(g0 + 91 - - - 41
oo +4 +4 +
s)llo!(a - 10 1)!
af ff
(D-1)1
Denote a' a 12-14 --,,'==f-1,7 -D-1 and 1/ lo 1. We have
1o
E2 Σ
Pa (los, 10,
D(S + 90 + [f + 90 + 91 +1
ED
a(a -
D-1
D(F + 90 + ( + 90 + 91 1)
Ep
D'-1'-1
(D' - SD' f' - d' - 1)!
Σ
D' (J' + 00 + 9 )]((( + + 91) - D'
==max(0,D'-2fi
(a'
(90 91 - 122) - + 1/2
(f' + 91 d' -1111 +4 - D' + +3)6o(aa - 1/2 1)!
a'l(f' d')1(D' - ff'
(D'-1)) -1)!
a(a 1(a-1)
Σ
Pa-1,--1.-- 12 9u. 91)
D-1
D(f + g + (f + 90 + 91 +1)
ED-1
a(a 1)
1
D(S 90 9I 9o + + + E 1,5 1.D-1
D
a(a - 1)
E.
D-1
Here the subscript means that are taking expectation w.r. the set sizes when the number of "0", "x" and " points is - 1 - 1, D 1). By symmetry, it can be shown similarly that
E1 = - (f a - 1) Ea D(F + + gi)(f 90 91 +1)
(ʃ - (f-a)(f- - a E.
D
D-1
Substituting above results into (26), we obtain
f-2 E-E -5....
i = =a 22
D-
To compute Fo. note that with a, and D, variable g2 is distributed as hyper( D D-f, D-) -- For F,, the distribution becomes hyper( () - 2, D f. D - 1). Since f + 9o 91 D 922, we deduce
D-1-1 Σ
(-- (D-
1
Eg
D(D (D
(D-1)
-0.
f-1-1 Σ
1
(D-f-1)) 1)!f!
(D- - f)((f - -1)! (D 1D11
D(D - (D - s + s! f f- - 2f +
21

---

Under review as a conference paper at ICLR 2022
and
D-f-1
(D-f-1) (D-1-
E
Σ
1
D(D - 8)(D - ++11
(D-1)
1mmax(0,D-2f44)
D-1-1
(D -- -2)!
Σ
D(D - 8) - 8 ++
(D-2) 2)!
D 2f+1)
fD- -
For VD 2 f, we have
D-1-1
-
(1-2)D-1(----2144
E
Σ
D
m=
(f1f-
(D- (D-f)l(f 1)!
s!(D - - 8-
----s--s(----- s) 21 +s}
(D 1-
(f - 2f - (D)))) 92))
E
Df(f - 1)(D-92)
92 +
(f-90 91)
<
E
Df(f + + 9o + 91
Consequently, we have
2
f 90 91
8n 2a(s a D(f + 9o + gf + 90 + 91 00++1 +1) Df + 90 + 91)
9o 91 1)
f 90
Df(f + 90 (f 90 + 91 +
=0,
and note that this holds for VD 2 K. The proof is complete.
A.6 PROOF OF THEOREM 3.5
Theorem 3,5 (Uniform Superiority). For any two binary vectors v, w E (0,1)" with J * or 1, it holds that V Var [Jar (v, w)] < V Var[JMH(U, w)].
Proof. By assumption we have < a < f. To compare Var[Jo, with Var[JaH]] J(1-J) K (K-1)J² _², it suffices to compare & with J², When D f. we know that the location vector k of (v, w) contains no elements. It is easy to verify that in this case, GGal | = [C2l = 0, and [oo follows hyper(ʃ 1, a, a 1). By Theorem 3.2, follows that when = S.
K
1 B[[Col] a(a - 1) JJ
E }
f(f -
Recall the definition j == -- which is always less than J. On the other hand, as D - co, we have
[Col 0, |C2l + a, Gool and | f a. We can easily show that
ED + J2 D
By Lemma 3.4, the sequence Ey, is strictly increasing. Since it is convergent with limit J2, by the Monotone Convergence Theorem we know that ED J2,YD f.
A.7 PROOF OF PROPOSITION 3.6
Proposition 3.6 (Consistent Improvement). Suppose J is fixed. In terms of the variance ratio
p(a) = Ver Ver[Jamm(uw is constant for any 0 < a < f.
VarlJa,((ww))
22

---

Under review as a conference paper at ICLR 2022
Proof. Let & be defined as in Theorem 3.2. Assume that D and f are fixed and is variable. Firstly, we can write the variance ratio explicitly as
J=
1- 1-J (K 1) )
p(a)
K
(K-1)E
J2
K
We now show that the term J - -(1 a). Then, for fixed and f. by cancellation p(a) would be constant for all 0 < a < f. We have
JJ: where C' is some constant independent of J (i.e.,
E a
flo
90 + l
Ea
+
J
f
aaf 90 + 91)
f+ 90 + 91
(J + 90 + 91) l - a5 + +22
E
af(ʃ + + 91)
aaaa Moo + 91) + a² + af9i 5210 a.l2
E
aʃ(} + 90 91)
a(a [00 + +1) + + 11) + ofgi -
E
af(ʃ + 90 + 91)
a(a- fgo + 91) + f(a f)lo + ofl a a h1)
E
(27)
af(ʃ 90 + 91)
where the constraints (10) that lo + + and I 91 + h1
We now study the
three terms respectively. We have
E
raaa [go + 91) -1 J)B of + gu 91)
A E'((1 J)- f f gu 91
90
We have shown the proof Lemma 3.4 that
Baf.D [
%o ( + gu 91
a(a - 1)
P a(a 1) D 1 E"
D E. fa-1,f-1,--1
f 90 91
and by symmetry it holds that
h1
(f a)(f a E*.
Ea...D
f + go + 91
D-1
Note that Since is fixed, (1Gol + [9 is distributed independent of Consequently, E' and E are both independent of a. Next, we obtain
f(a - f E
af(f + gu + 91) - f(a- E D-1
and
af(f -flf-a-hij - (1
J)JE -1- -1 f(f
-f a - 1) F.a
E
af( 90 91)
D-1
Summing up the terms and substituting into (27), we derive
E C(1 C(1-),
-
where C -E f(f-2) D-1 E*, which is independent of a. Taking into p(a), we get
1 1- p(a) = -- - (K - ()((1-J] = 1- - 1)C
1
which is constant only depending on f, D and K. This completes the proof.
23

---

Under review as a conference paper at ICLR 2022
A.8 PROOF OF THEOREM 5.1
Proof. Denote [[ := (()()((v) = hx (w)H for any 1 < k I K. We first recall some notations.
We have v, w E [0,1)2 and and f are defined (5). Denote B1 = {i a; = 0}, Bg { a; = x) and B3 {i: a; = -} the sets of three types of points, respectively. For a S j S D
and S I K, define
A- (i) (a; (i+ k - mod D) + 1s
(+) {a, (i + k 1 mod D) + ++> 5)-
Let n n0, [2, = 0 A- A- be the number of "O" points in A- (j). Analogously let n- -=2(j) nj).nn_3ll
be the number of "x" and "-" points in A- (j), and (z), nn 2(,)(()),)))) m4.3(j) be
the number of "0", "x" and "-" points in (4). For any i, denote i" (i + k mod D) + 1,
i# (i fi-ke k 1 mod D) 1.
Our analysis starts with the decomposition hash collision probability,
D P ha((v) = hw(w) = =g]
E[1a] P Plha(o)) = ha (w))
Σ
(28)
where recall h()) is the hash sample. Consider the process for generating the hash. As before, we look at the location vector æ. In Method 2, we first permute æ by π to get ((r). Then the k-th hash samples collide if the minimum of (==() is "O". One key observation is that, when applying & the random index for the i-th element in (xx) is exactly the one used for ø; (shifted backwards) in the initial permutation. A toy example in provided in Figure 8 to help understand the reasoning.
j=4
: M.k
A_
X
(x))
Figure 8: Illustration of C-MinHash-(r, x) hash collision, with k 2. Here, "circulant right" means "circulant down". Small indices correspond to upper elements.
Further denote set M (i) (ii & B₂) be the collection of indices of initially permuted vector Tx)) that not <_ points, and M (M- - k mod D) + 1 be the corresponding indices shifted backwards. In Figure 8, M = {2, 5, 8, 11}. Also, π (6) = 4, and the permutation maps are described by the red arrows. Consequently, in (=)),, the 8-th element ("O") in r(x)) will be permuted to the same index the 8 2 = 6-th element in æ. which equals to 4. It is important to notice that, when considering the k-th collision, only points in M. matters. Hence, we deduct:
(Collision condition) Denote i = arg min π (xxx be the location of minimal permu- tation index in M. The k-th collision occurs at j i.f.f. T()) = j. and the i--th element in (x) must be "O" point. Recall the definition i" = (i k 1 mod D) 1.
24

---

Under review as a conference paper at ICLR 2022
In Figure 8, consider = 6 and j for example. Above condition means that the 6-th element in æ ("-" in red bold border) is permuted to the j = 4-th position, and it is above all other permuted elements with red bold borders. Meanwhile, the + k 6 + 2 8-th element in T(x) must be "O". Figure& 8 exactly satisfies the condition, so depicts a collision. Mathematically, we have
D
E[1+]
Σ
P
h)(())
= hx(w) = s]
D
D
Σ
j. n (1) j. (1²) E B1}.
(29)
where i arg minggM... Tw;)). In this expression, everything is random of π, except for the set B] which is fixed given the data.
Now we will focus on deriving the probability for fixed and in (29). Our analysis will be conditional on the collection of variables Z which is defined as follows. Let 2-,1, 2-,2 and 2-,3 be the number of "O", "x" " and " points in (j) n M and 2+,1, 24.2 and 24.3 be the number of "O", "x" and " "_" points in A, (i) ( respectively. Here M represents the complement of M, Notice that Z (and its density function) depends on different j since (j) and A+ (j) depends on j. For the ease of notation we suppress the information of j in Z (and z's). It is easy to see that Z (=_, 2+,A (1) follows hyper(D, D - f, n- (i)l n+ (i)l.) Denote the domain of
Z and G, Conditional on Z. we obtain
D
D
B[1N|
Σ
n = j ((*) B,1 P3 [ [
j=1
ZEO,
i=1
D
1
= 512 312]11 [x]
j=1 ZEO, i=1
D T( [2]
-
Σ ZEO i=1
(30)
with i arg min T(x)). We will carefully compute the probabilities in the summation. Basically, the key is that elements in M need to be controlled, i.e. smaller than j. and other positions can be arbitrary. Given Z, this means that we need put 11 =a 2_,1 2+,1 type "O" points, T2 = f 2-,2 2+,2 type "x" points and r3- = D D - 2- 24.3 type points no smaller than j. with x (() j exactly. Also note that there are fixed by Σx= 2+,6 type "_" points no smaller than j.
With all these definitions and reasoning, we ready proceed with the proof. Based on æ; we have three general cases.
1) a E B1- The first case is that x; O.
Case la) j < 1". Firstly, we consider the case where j < i". By combinatorial theory we have
P (1) = -1z] P (1) = j|ز - & B3, Z π (f) & B Z
(4) (PTT)L)) 1)
N (5)
(G) $ Bz|Z]
ri 72 (D-J) 1itt2
4 P P - & Ba1Z.
(31)
where the second probability is that the j-th element in T(x)) is not "_" Conditional on Z, the probability is dependent on j#:;
3
P ा
(1) E B3|Z] = Σ 165# E BBp(11
z-p
1=1
25

---

Under review as a conference paper at ICLR 2022
Combining with (31) obtain
3 Pi
P(T(0) = =iz]
Σ p=1
15 E Bp
2-p ワー
(32)
Next we compute P(T Bi Bi|+(()
ZJ. Note that given the conditions, πT (i*) has two cases: 1) it comes from M (i.e. it is one of the elements with red bold border); 2) Otherwise. We then can write
E
B π (i') E M (t) ( J.
P
(i") E B1 | (i') & M k:
- (1)))))))))) (1
-11 2+.1
11 +2
11
n1 12 -1
a a-n
(i)
D- 00
ri + r2 -
D - j- bo
/ r- -2
A Z+,1
ri r-
11 + 12
+(1
(1)
D D-j-1 by
D - bo
A (1
2+.1
JJ.
(33)
m+,
Combining (32) and (33), we obtain when i B1 and j <,.
((i))) = Ent E 8,](1
2- [(1
2+,1 )P.J..
(34)
n1.,1 (j)
Case 1b) j = i". Similarly approach also applies to the situation with j j= =" In this case,
p - ( & Ba || = (1 2-,1 Pp.
(i)) B, (1)) = j. Z| = 1.
(35)
The equations are because (i*)# = i E B1, and equivalently, x- (i") = - 1 = i B. Case 1e) it. this case, we still have
P[m(0) = 51z]
2-p - E Bp1(1 n=
p=1
but the probability of of 1-111") (i*) being "O" is different. Since j j>> i", this event now depends z-
p = 3, More specifically,
P( (i*) E Bi(T(H j, Z|
1 B1
2-,1
Σ 165 E B,)
z-p
J
n n_
2=3,
Therefore, when i B₁ and j > jr, it holds that
2-p )
z-,1 [(i,j) = (1 (i) 1(j# BB m=
2-,1 1
+ Σ 1(j# E B1
Jr.
2,3
(36)
2) æ; E B2. The case where x; E B2 can be analyzed using similar arguments. For conciseness, we mainly present the final results.
Case 2a) j < 1" The calculation ends up in the same form. We have
p p( = 5|z]
P
Σ 1
B,
Z-pp n
(i)
p=1
26

---

Under review as a conference paper at ICLR 2022
with P- Pi. In addition,
π (i) [i( = j.2
= -,2]==((
2+ JJ2.
2+.((i)
where J22 Dーjーb + (1 Dーj-by )d* Hence, when æi B2 and j < 8", we have
[(t,)) = 1100==10p 101 E EB11(1 p=1
2-p (1 n=,p(j) nt,2(j)
24,2
PP.J2.
(37)
Case 2b); j = 1. In this case, ji simply equals to 0, since π (i²)) = =i- E B2. The probability of π (i") being "O" is O.
Case 2c) j > i" Omitting the details, we have
[(i,)) (1 2-2(
2_ 111 E (1)
2_,2 ) Σ n--2(i)-1 p=1.
155 E Bp
z-p
J
n x0)
(38)
2) a; E B3.
Case 3a) < <." The expression is different from previous two, in that need π -- (j) B3.
P[T(0) = =1 = P[((1) = ((i) E B3, 2 P π (f) E Ba
= Ps Σ 115* E BBp) z-
p=1
where
1 ( (r--1) ritr2
( (D-j-bo)
P3
13 (D-1) (1
Moreover, we have
P π (1") E Bi((()) = - (1
2+,3 Jss.
n+,((j)
with J3-
m D- bo
+ (1 ) )r Combining parts together we obtain
m(i,)) = Σ 10 Bp)
Z_.p (1
2n,3
PaJa.
(39)
n (j) nt,3(i)
Case 3b) j i" By same reasoning as Case 2a), [i 0.
Case 3c) j > i* We have in this case
[(i.j) =
1 E B3}
2-33 n (1) - 2-
+ (1
2_,3 Σ
111
E =Bp)
2-
n_, n2,3(
1
n
1=1.2
3 Σ pml
1 # Bp) n n., (1
2-,9
2_,3 nー
1pp = 3}
1 = =3)
(40)
Finally, combining (30), (34), (35), (36), (37), (38), (39) and (40) and re-organizing terms, the proof is complete.
27

---

Under review as a conference paper at ICLR 2022
B MORE NUMERICAL JUSTIHICATION ON C-MINHASH-
The "Words" dataset (Li & Church, 2005) (which is publicly available) contains a large number of word vectors, with the i-th entry indicating whether this word appears in the i-th document, for total of D 2 documents. The key statistics of the 120 selected word pairs are presented in Table I. Those 120 pairs of words are more less randomly selected except that we make sure they cover wide spectrum of data distributions. Denote d as the number of non-zero entries in the vector. Table I reports the density d = d/ D for each word vector, ranging from 0.0006 to 0.6. The Jaccard similarity J ranges from 0.002 0.95.
In Figures 16, we plot the empirical MSE along with the empirical bias² for Jr. as well as the empirical MSE for Ja Note that for D this large, it is numerically difficult to evaluate the theoretical variance formulas. From the results in the Figures,
observe
For all the data pairs, the MSE of C-MinHash-(m, T7 estimator overlaps with the empirical MSE of C-MinHash (o, т) estimator for all from up to 4096.
The bias? is several orders of magnitudes smaller than the MSE, in all data pairs. This verifies that the bias of Jr.= is extremely small in practice and can be safely neglected.
We have many more plots more data pairs. Nevertheless, believe the current set of experiments on this "Words" dataset should be sufficient to verify that, the proposed C-MinHash-(rr. σ) could give indistinguishable Jaccard estimation accuracy in practice compared with C-MinHash-(or; IT)
28

---

Under review as a conference paper at ICLR 2022
120 selected word pairs from the Words dataset (I.i & Church, 2005). For each pair, report the density d (number of non-zero entries divided by D 226 for each word as well as the Jaccard similarity J. Both d and J cover wide range of values.
Table 1:
d1
d2
d₁
d2
J
ABOUT - INTO
0.302
0.125
0.258
NEW WEB
0.291
0.194
0.224
ABOUT - LIKE
0.302
0.140
0
NEWS - LIKE
0.168
0.140
0.172
ACTUAL DEEVELPPED
0.017
0.030
0.071
NO WELL
0.220
0.120
0.244
ACTUAL GRABBED
0,017
0.002
0.016
NOT IT
0,281
0.295
0.437
AFTER OR
0.103
0.356
0.220
NOTORIOUSLY LOCK
0.0006
0.006
0.004
AND PROBLEM
0.554
0.044
0.070
OF- THEN
0,570
0.104
0.168
AS NAME
0.280
0.144
0.204
OF- WE
0.570
0.226
0.361
AT - CUT
0.374
0.242
0.052
OPPORTUNITY COUNTRIES
0.029
0.024
0.066
BE - ONE
0,323
0.221
0,403
OUR THAN
0.244
0.125
0.245
BEST AND
0.136
0.554
0.228
OVER BACK
0,148
0. 06060
0.233
BRAZIL OH
0.010
0,031
0.019
OVER TWO
0.148
0.121
0.289
BUT MANY
0.167
0.116
0.340
PEAK SHOWS
0.006
0.033
0.026
CALLED- BUSINESSES
0.016
0.018
0.043
PEOPLE BY
0.121
0,425
0.228
CALORIES MICROSOFT
0.002
0.045
0.0003
PEOPLE INFO
0.121
0.138
0.117
CAN FROM
0.243
0.326
0.444
PICKS BOOST
0.007
0.005
0.007
CAN SEARCH
0.243
0,214
0.237
PLANET REWARD
0.013
0.003
0.018
COMMITTED PRODUCTIVE
0,013
0.004
0.029
PLEASE MAKE
0.168
0.141
0.195
CONTEMPORARY FLASH
0.011
0.021
0.013
PREFER PUEDE
0.010
0.003
0.0001
CONVENIENTLY INDUSTRIES
0.003
0.011
0.009
PRIVACY FOUND
0.126
0.136
0.053
COPYRIGHT AN
0.218
0.290
0.209
PROSECUTION MAXIMIZE
0.002
0.003
0.006
CREDIT-CAM
0.046
0,041
0.285
RECENTLY INT
0.028
0.007
0.014
DE WEB
0.117
0.194
0.091
REPLY ACHIEVE
0.013
0.012
0.023
DO GOOD
0.174
0.102
0.276
RESERVED BEEN
0.172
0.141
0.108
EARTH GROUPS
0.021
0.035
0.056
RIGHTS FIND
0.187
0.144
0.166
EXPRESSED FRUSTRATED
0,010
0.002
0.024
RIGHTS RESERVED
0.187
0.172
0.877
FIND HAS
0,144
0.228
0.214
SCENE ABOUT
0.012
0.301
0.029
FIND SITE
0,144
0.275
0.212
SEE- ALSO
0.138
0666
0.291
FIXED SPECIFIC
0.011
0.039
0.054
SEIZE ANYTHING
0.0007
0.037
0.012
FLIGHT- - TRANSPORTATION
0,011
0.018
0.040
SHOULDERS. -GORGEOUS
0,003
0.004
0.028
FOUND DE
0.136
0.117
0.039
SICK FELL
0.008
0.008
0.085
FRANCISCO SAN
0.025
0.049
0.476
SITE CELLULAR
0.275
0.006
0.010
GOOD BACK
0.102
160
0.220
SOLD LIVE
0.018
0.064
0.055
GROUPS- ORDERED
0.035
0.011
0.034
SOLO - CLAIMS
0.010
0.012
0.007
HAPPY CONCEPT
0.029
0.013
0.054
SOON ADVANCE
0.040
0.017
0.057
-IRST-IRST
0,267
0.151
0.320
SPECIALIZES -ACCAALZES-ACTUAL ACTUAL
0.003
0.017
0.008
HAVE US
0.267
0.284
0.349
STATE- OF
0.101
0.570
0.165
HILL- ASSURED
0.020
0.004
0.011
STATES UNITED
0.061
0.062
0.591
HOME SYNTHESIS
0.365
0.002
0.003
TATTOO JEANS
0.002
0.004
0.035
HONG KONG
0.014
0.014
0.925
THAT- ALSO
0,301
0.166
0.376
HOSTED DRUGS
0.016
0.013
0.013
THIS CITY
0.423
0.123
0.132
INTERVIEWS. FOURTH
0.012
0.011
0.031
THEIR- SUPPORT
0.165
0.117
0.189
KANSAS - PROPERTY
0.017
0.045
0.052
THEIR- VIEW
0.165
0.103
0.151
KIRIBATI- GAMBIA
0.003
0.003
0.712
THEMM OF
0.112
0.570
0.187
LAST - THIS
0.135
0.423
0.221
THEN- NEW
0.104
0.291
0.192
LEAST ROMANCE
0.046
0.007
0.019
THINKS LOT
0.007
0.040
0.079
LIME- REGISTERED
0.002
0.030
0.004
TIME OUT
0.189
0.191
0.366
LINKS TAKE
0.191
105
1.1
TIME WELL
0.189
0.
0.299
LINKS THAN
0.191
0.125
0.141
TOP- AS
0.140
0.280
0.217
MAIL- AND
0.160
0,554
0.192
TOP- COPYRIGHT
0.140
0.218
0.149
MAIL- BACK
0.160
060
0.132
TOP- NEWS
0.140
0.168
0.192
MAKE LIKE
0.141
0.140
0.297
AND
0.200
0.554
0.334
MANAGING LOOC
0.010
0.006
0.010
-P-HAS
0,200
0.228
0.312
MANY US
0.116
0.284
0.210
US BF
0.284
0.323
0.335
MASS- DREAM
0.016
0.017
0.048
VIEW- IN
0.103
0.540
0.153
MAY- HELP
0.184
0.156
0.206
VIEW PEOPLE
0.103
0.121
0.138
MOST HOME
0.141
0.365
0.207
WALKED ANTIVIRUS
0.006
0.002
0.002
NAME IN
0.144
0.540
0.207
WEB GO
0.194
0.111
0.138
NEITHER - -FIGURE
0.011
0.016
0.085
WELL- INFO
0.120
0.138
0.1
NET SO
0.101
0.154
0.112
WELL- NEWS
0.120
0.168
0.161
NEW PLEASE
0.291
0.168
0.205
WEEKS- LONDON
0.028
0.032
0.050
29

---

Under review as a conference paper at ICLR 2022
109
10
109
Perm Perm
Perm
Perm
1
10.2
Perm Blas
10
Perm
..... Blas
Blas
MSE
10
WELL INFO
MSE
ABOUT INTO
MSE
10
ABOUT LIKE
10
10.8
10
10
10.8
10.8
10
10
10
10
10
10
10
10
10
10
10
10'
10
10
10
K
10
100
109
2 Perm
Perm
Perm
2
10
10
Blas
Blas
MSE
10-
WELL NEWS
MSE
10"
MSE
10
ACTUAL GRABBED
ACTUAL DEVELOPED
10
10
10
10
10.8
10
100
10
10
10
10
10
10
10
10
10
10
10
10
10
10
K
K
K
10
10
100
2 Perm
Perm
Perm
2
Perm
10
Perm
10
Perm
Blas
Blas
Blas
MSE
10-4
AFTER OR
MSE
10"4
AND PROBLEM
MSE
NAME
10.8
10.8
10.8
Am
10
10
1
10
10
10
10
10
10
10
10
10
10
10
10
K
K
10
10
109
2 Perm Perm
Perm
Perm
10
10
Perm
Blas
2
Bias
2
Bias
MSE
10
MSE
10-4
MSE
10
BEST AND
BE ONE
1
CUT
10-8
10.6
10
10
10
10
10
102
10
10
10
10
10
10
10
10
10'
10
10a
10
K
K
K
10
10
100
2 Perm
Perm
Perm
10
Perm
10
Perm
10
Perm
..... Blas
H... Bias?
Blas
MSE
10-1
MSE
10-4
MSE
10
BRAZIL OH
BUT MANY
CALLED BUSINESSES
10
10.6
10
10 8
10:8
10
10
10!
1
1
4
10
10
1
10a
10
10
10
10
103
10
K
Figure 9: Empirical MSES C-MinHash-(Tr, T) ("1 Perm", red, solid) vs. C-MinHash- m ("2 Perm". blue, dashed) on various data pairs from the Words dataset. We also report the empirical bias? for C-MinHash-(ar (Tr, w) to show that the bias so small that can be safely neglected. The empirical MSE curves for both estimators essentially overlap for all data pairs
30

---

Under review as a conference paper at ICLR 2022
109
10
109
2 Perm
Perm
Perm
1
Perm
10.2
Perm
10
Perm
Blas
Blas
Blas
MSE
10
CALORIES MICROSOFT
MSE
CAN FROM
MSE
10
CAN SEARCH
10
10.8
10
10.8
10.8
10.8
A
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
K
10
100
109
2 Perm
Perm
Perm
2
10:2
10
Blas
Blas
MSE
10-4
MSE
10"
CONTEMPORARY FLASH
MSE
10
CONVENIENTLY INDUSTRIES
COMMITTED PRODUCTIVE
10
10
10
10
10.8
10
A.
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10%
K
K
K
10
10
100
2 Perm
Perm
Perm
2
Perm
10
Perm
10
Perm
Blas
"Blas
Blas
MSE
10-4
COPYRIGHT AN
MSE
10"4
CREDIT CARD
MSE
DE WEB
10.8
10.8
10.8
10
10
10
10
10
10
10
10
10
10
10
10
10
103
10
K
10
10
109
2 Perm Perm
Perm
Perm
10
10
Perm
10
Perm
Blas
2
Bias
2
Bias
MSE
10
DO- GOOD
MSE
10-4
EARTH GROUPS
MSE
10
EXPRESSED FRUSTRATED
1
10.6
10.6
10
10
10
10
10
102
10
10
10
10
10
10
10
10
10'
10
10
10
K
K
K
10
10
109
2 Perm
Perm Perm
Perm
10
Perm
10
10
Perm
Blas
.... Bias?
Bias
MSE
10-1
MSE
10-4
MSE
10
FIXED SPECIFIC
FIND HAS
FIND SITE
1
10.6
10
10
BAA
10
..
10
18.
10
10
10
1
4
10
10
2
10
10
10
10
10
103
10
K
Figure 10: Empirical MSEs of C-MinHash-- T) ('1 Perm", red, solid) vs. C-MinHash- T)) ("2 Perm". blue, dashed) on various data pairs from the Words dataset. We also report the empirical bias for C-MinHash-(an w) to show that the bias so small that can be safely neglected. The empirical MSE curves for both estimators essentially overlap for all data pairs
31

---

Under review as a conference paper at ICLR 2022
100
10
100
2 Perm
Perm
Perm
1
Perm
10
Perm Blas
10
Perm
Blas
Blas
MSE
10
FLIGHT TRANSPORTATION
MSE
FOUND DE
MSE
FRANCISCO SAN
10
10.8
8
10.8
10.8
A.A
100
10
1
10
10
10
10
10
10
10
10
10
10
10
10
K
10
100
100
2 Perm
Perm
Perm
2
10:2
10
Blas
Blas
MSE
10-
GOOD BACK
MSE
10"
MSE
10
HAPPY CONCEPT
10
10
GROUPS ORDERED
10
10.8
10.8
10
100
10
10
10
10
10
10
10
10
10
10
10
10
10
10
K
K
K
10
10
100
2 Perm
Perm
Perm
2
Perm
10
Perm
10
Perm
Blas
"Blas"
Blas
MSE
10
HAVE FIRST
MSE
10"4
HAVE US
MSE
10
HILL ASSURED
10.8
10.8
10.8
10
10
10
1
10
10
10
10
10
10
10
10
10
103
10
K
K
10
10
109
2 Perm Perm
Perm
Perm
10
10
Perm
10
Perm
Blas
2
Bias
2
Bias
MSE
10-4
MSE
10-4
HONG KONG
MSE
10
HOME SYNTHESIS
HOSTED DRUGS
1
10-6
10.6
10
10
10
10
10
102
10
10
10
10
10
10
10
10
10
10
10a
10
K
K
K
10
10
109
2 Perm
Perm
Perm
2
Perm
10
Perm
10
Perm
Blas?
Blas?
Blas
MSE
10-1
INTERVIEWS FOURTH
MSE
10-1
KANSAS-PROPERT
MSE
10-1
KIRIBATI GAMBIA
10
10-
10
10 8
10 8
10
10
10
10
10
4
10
10
10
10a
10
10
10!
10
103
10
K
Figure 11: Empirical MSEs of C-MinHash-- m) ('1 Perm", red, solid) vs. C-MinHash- T) ("2 Perm". blue, dashed) on various data pairs from the Words dataset. We also report the empirical bias? for C-MinHash-(an w) to show that the bias so small that can be safely neglected. The empirical MSE curves for both estimators essentially overlap for all data pairs
32

---

Under review as a conference paper at ICLR 2022
109
10
100
Perm Perm
Perm
Perm
1
10
Perm
10
Perm
..... Blas
Blas
Blas
MSE
10
LAST THIS
MSE
MSE
10
10
10.8
LEAST ROMANCE
10
LIME REGISTERED
10.8
10.8
10.8
100
10
1
10
10
10
10
10
10
10
10
10
10
10
10
K
10
10
109
2 Perm
Perm
Perm
2
10:2
10
Blas
Blas
MSE
10"
LINKS TAKE
MSE
10"
LINKS THAN
MSE
10
MAIL AND
10
10
10
10
10.8
10
100
10
10
10
10
10
10
10
10
10
10
10
10
10
10%
K
K
K
10
10
100
2 Perm
Perm
Perm
2
Perm
10
Perm
10.2
Perm
Blas
"Blas
.... Blas
MSE
10-4
MAIL BACK
MSE
10"4
MAKE LIKE
MSE
10
MANAGING LOCK
10.8
10.8
10.8
AM
10
10
1
10
10
10
10
10
10
10
10
10
10
10
10
K
10
100
109
2 Perm Perm
Perm
Perm
10
10
10
Perm
Blas
2
Bias
2
Bias
MSE
10
MANY US
MSE
10-4
MSE
10
MAY HELP
MASS DREAM
1
10-6
10
10
10
10
2/A
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
K
K
K
10
10
109
2 Perm
Perm Perm
Perm
10
Perm
10
10
Perm
..... Blas?
Bias?
Blas
MSE
10-1
MOST HOME
MSE
10-4
NAME IN
MSE
10
NEITHER FIGURE
10
10.6
10
10
8
10
10
10
1
10
4
10
10
10
10a
10
10
10
10
103
10
K
Figure 12: Empirical MSEs of C-MinHash-- T) ('1 Perm", red, solid) vs. C-MinHash- π) ("2 Perm". blue, dashed) on various data pairs from the Words dataset. We also report the empirical bias? for C-MinHash-(an s) to show that the bias so small that can be safely neglected. The empirical MSE curves for both estimators essentially overlap for all data pairs
33

---

Under review as a conference paper at ICLR 2022
100
10
100
Perm Perm
Perm Perm
Perm
1
10:2
10
Perm
Blas
Blas
Blas
MSE
10
NET SO
MSC
NEW PLEASE
MSE
10
NEW WEB
10
10.8
10
10
10.8
10.8
AA
100
10
10
10
10
10
10
10
10
10
10
10
10
10
10
K
10
100
109
2 Perm
Perm
Perm
2
10:2
10
Blas
Blas
MSE
10-
NEWS LIKE
MSE
10"
WELL
MSE
10
NOT IT
10
10
10
10
11.
10.8
31 67.
10
100
10
10
10
10
10
10
10
10
10
10
10
10
10
10
K
K
K
10
10
100
2 Perm
Perm
Perm
10
Perm
10
Perm
10
Perm
Blas
Blas
Blas
MSE
10-4
MSE
10"4
OF - THEN
MSE
OF WE
NOTORIOUSLY LOCK
10.8
10.8
10.8
D6.
10
10
10
10
10
10
10
10
10
10
10
10
10
10a
10
K
K
10
10
109
2 Perm
Perm
Perm
1 2
Perm
10
Perm
Blas
2
Bias
2
Bias
MSE
10
OPPORTUNITY COUNTRIES
MSE
10-4
MSE
10
OUR THAN
1
10-6
WALKED ANTIVIRUS
10.6
10
10
10
Wh
A
10
10
102
10
10
10
10
10
10
10
10
10
10
10a
10
K
K
K
10
10
109
2 Perm Perm
Perm Perm
Perm
10
10
10
Perm
Blas?
Bias?
Bias
MSE
10-1
OVER BACK
MSE
10-4
OVER TWO
MSE
10
PEAK SHOWS
10-6
10
10 8
10
10
J.
10
10
1
10
10
10
10
10
10a
10
10
10
10
103
10
K
Figure 13: Empirical MSEs of C-MinHash-- T) ('1 Perm", red, solid) vs. C-MinHash- T) ("2 Perm". blue, dashed) on various data pairs from the Words dataset. We also report the empirical bias for C-MinHash-(an s) to show that the bias so small that can be safely neglected. The empirical MSE curves for both estimators essentially overlap for all data pairs
34

---

Under review as a conference paper at ICLR 2022
109
10
100
-2 Perm Perm
Perm Perm Blas
Perm
1
10
10
Perm
..... Blas
... Blas
MSE
10
PEOPLE BY
MSE
PEOPLE INFO
MSE
10
PICKS BOOST
10
10.8
10
10.8
10.8
10.8
AA PE
100
10
10
10
10
10
10
10
10
10
10
10
10
10
10
K
10
10
100
2 Perm
Perm
Perm
2
10:2
10
Blas
BBla
MSE
10-
MSE
10
PLEASE MAKE
MSE
10
PLANET REWARD
PREFER PUEDE
10
10
10
10%
10.8
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10%
K
K
K
10
10
10
2 Perm
Perm
Perm
2
Perm
10
Perm
10
Perm
Blas
Blas
Blas
MSE
10
PRIVACY-FOURT
MSE
10"4
MSE
RECENTLY INT
PROSECUTION MAXIMZE
10.8
10.8
10.8
W
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
K
K
10
10
109
2 Perm Perm 2
Perm
Perm
2 2
10
Perm
10
Perm
Blas
Bias
2
Bias
MSE
10
REPLY ACHIEVE
MSE
10-4
RESERVED BEEN
MSE
10
RIGHTS FIND
10.6
10-8
10.6
10
10
10
10
10
102
10
10
10
10
10
10
10
10
10'
10
10
10
K
K
K
10
10
109
2 Perm
Perm
Perm
10
Perm
10
Perm
10
Perm
Blas?
Blas?
Blas
MSE
10-1
RIGHTS RESERVED
MSE
10-4
MSE
10-
SEE ALSO
SCENE ABOUT
10-
10
10 8
8
MAA
10
10
10
2
1
1
10
10
102
10a
10
10
10!
10
103
10
K
Figure 14: Empirical MSEs of C-MinHash-- T) ('1 Perm", red, solid) vs. C-MinHash- T) ("2 Perm". blue, dashed) on various data pairs from the Words dataset. We also report the empirical bias? for C-MinHash-(an w) to show that the bias so small that can be safely neglected. The empirical MSE curves for both estimators essentially overlap for all data pairs
35

---

Under review as a conference paper at ICLR 2022
109
10
109
2 Perm Perm Blas
Perm
Perm Perm
1
10.2
Perm
10
Blas
Blas
MSE
10
MSE
SHOULDERS GORGEOUS
MSE
10
SEIZE ANYTHING
SICK FELL
10
10.8
10
10
10.8
10.8
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
K
10
10
109
2 Perm
Perm
Perm
2
10:2
10
Blas
"Blas
MSE
10
MSE
10"
SOLD LIVE
MSE
10
SOLO CLAIMS
SITE CELLULAR
10
10
10
10
10.8
10
100
10
10
10
10
10
10
10
10
10
10
10
10
10
10
K
K
K
10
10
100
2 Perm
Perm
Perm
2
Perm
10
Perm
10
Perm
Blas?
BBas
Blas
MSE
10
SOON ADVANCE
MSE
10"4
SPECIALIZES ACTUAL
MSE
STATE OF
10.8
10.8
10.8
10
10
10
10
10
10
10
10
10
10
10
102
10
10
K
K
10
10
109
2 Perm Perm
Perm
Perm
2
10
Perm
Blas
2
Bias
2
Bias
MSE
10
STATES UNITED
MSE
10-4
MSE
10
THAT ALSO
1
10-8
TATTOO JEANS
10.6
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10a
10
K
K
K
10
10
109
2 Perm Perm
Perm
Perm
10
10
Perm
10
Perm
Blas?
Bias?
Blas
MSE
10-1
THIS CCTSY
MSE
10-4
THEIR SUPPORT
MSE
10
THEIR THEIR-VIEW
10
10.6
10
10 8
10
10
10!
10
1
10
10"
10
10
10
10
10!
10
103
10
K
Figure 15: Empirical MSEs of C-MinHash-- T) ('1 Perm", red, solid) vs. C-MinHash- T) ("2 Perm". blue, dashed) on various data pairs from the Words dataset. We also report the empirical bias? for C-MinHash-(an s) to show that the bias so small that can be safely neglected. The empirical MSE curves for both estimators essentially overlap for all data pairs
36

---

Under review as a conference paper at ICLR 2022
109
10
109
Perm Perm
Perm
Perm
1
10.2
Perm
10
Perm
................................ Blas
Blas
Blas
MSE
10
THEM OF
MSE
THEN NEW
MSE
10
THINKS LOT
8
10.8
10
10
10.8
10.8
31
10
10
10
10a
10
10
10
10
10
10
10
10'
10
10
10
K
10
100
109
2 Perm
Perm
Perm
2
10:2
10
Blas
Blas
MSE
10"
TIME OUT
MSE
10
TIME WELL
MSE
10
TOP-
10
10
10
10
10.8
10
Bue 6.WW
10
10
10
10
10
10
10
10
10
104
10
10
10
10
10
K
K
K
10
10
100
2 Perm
Perm
Perm
2
Perm
10
Perm
10
Perm
Blas
Blas
Blas
MSE
10-4
TOP COPYRIGHT
MSE
10"4
TOP NEWS
MSE
UP - AND
10.8
10.8
10.8
A
10
10
10
10
10
10
10
10
10
10
10
10
102
10
10
K
K
10
10
109
2 Perm Perm 2
Perm
Perm
10
10
10
Perm
Blas
Bias
2
Bias
MSE
10-4
UP-
MSE
10-4
BE
MSE
10
VIEW IN
10.6
10.6
10.6
10
10
10
10
10
102
10
10
10
10
10
10
10
10
10
10
10
10
K
K
K
10
10
100
2 Perm
Perm
Perm
10
Perm
10
Perm
10
Perm
..... Blas?
Bias?
Blas
MSE
10-1
VIEW PEOPLE
MSE
10-1
WEB- GO
MSE
10
WEEKS - LONDON
10-6
10
10
8
10:8
10
10
10
102
1 1
10
10
1
10a
10
10
10
10
103
10
K
Figure 16: Empirical MSEs of C-MinHash-- m) ('1 Perm", red, solid) vs. C-MinHash- T) ("2 Perm". blue, dashed) on various data pairs from the Words dataset. We also report the empirical bias for C-MinHash-(ar (Tr, w) to show that the bias so small that can be safely neglected. The empirical MSE curves for both estimators essentially overlap for all data pairs
37


Reviews:
[{"review_id": "xi3zMiP7Cw7", "reviewer": "Reviewer_7874", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an interesting and surprising result as the algorithm is neat and simple, and improves on a classical algorithm. The proof seems straightforward with laborious calculations, which I did not check carefully. Hence, intuition as to why it works is important. Unfortunately, the paper does not provide the intuition at all and I hope the authors can elaborate on this.\n\nFrom an algorithmic perspective, since the variance depends on the Jaccard similarity itself, one can only assume the worst case that the variance is 1/(4K) and pick K accordingly to obtain an (1+/-eps)-approximation. The new variance in Theorem 3.1 has an almost intractable non-closed expression for the variance. How does one choose K now? Is there a neater (though weaker) upper bound for the variance in Theorem 3.1?\n", "summary_of_the_paper": "The paper designs an improved version of the classical MinHash data structure for calculating the Jaccard similarity between two binary strings.\n\nThe classical MinHash data structure generates K hash values for a binary string by generating K independent random permutations of the binary string and taking the index of the first “1” in the permuted string as the hash value in each random permutation. The estimator is then the percentage of equal hash values out of K hash values for the two binary strings. This is an unbiased estimator.\n\nThis paper’s algorithm, called C-MinHash, first applies a random permutation to the binary string. For the K hash values, instead of using K independent random permutations, the new algorithm uses the same permutation but shifted by 1, 2, …, K positions. The estimator is the same as that of the MinHash and can be easily shown to be unbiased. The paper then shows that this simple scheme, with only two independent random permutations, yields a smaller variance than that of MinHash.\n", "summary_of_the_review": "Personally I like the paper and I hope that the paper will be accepted. ~However, I strongly feel that this paper should probably be merged with a separate paper by the same authors on reducing two permutations to one to tell a full story. I had a look at the arXiv version (https://arxiv.org/pdf/2109.04595.pdf) of the other paper and the main proof is just 4 pages. There is no compelling reason to split them into two papers. ~\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "pgGDP_0dTxA", "reviewer": "Reviewer_89pE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The fact that using two permutations provides smaller than vanilla MINHASH is interesting, and the theoretical analysis of the paper is extensive. I think the paper can improve in the following perspective. \n1. There are some works on improving MINHASH, such as one permutation hashing and densifying one permutation hashing. The relation between MINHASH and these works needs to be thoroughly discussed. Instead, the paper only says C-MINHASH can be used to improve one permutation hashing. Moreover, experiments should also be conducted to compare with these works.\n2. The benefits of using only two permutation is not well justified. Existing works (one permutation hashing and densifying one permutation hashing) only need to conduct permutation once while MINHASH still needs to conduct permutation K times. The storage cost may not be a concern as one can generate random permutations on the fly without storing them.\nI will raise my score if the concerns are addressed.    \n", "summary_of_the_paper": "This paper proposes C-MINHASH to improve vanilla MINHASH. Instead of using K random permutations to generate K hash values, C-MINHASH requires only two permutations. Theoretically, C-MINHASH provides unbiased estimate, and its variance is smaller than MINHASH. Extensive empirical experiments verify the theoretical analysis. ", "summary_of_the_review": "The method and theoretical analysis are interesting. However, the paper lacks a clear justification of the benefits of C-MINHASH and a through comparison with related works.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "llYfD4MWdsk", "reviewer": "Reviewer_yZFL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1. I like the idea of using circulation and shifting for the hashing strings, which can reduce the number of permutations but still introduce randomness (even though not entirely independent).\n\n2. The authors systematically show that C-MinHash-($\\sigma$,$\\pi$) has uniformly lower Jaccard estimation variance than the vanilla MinHash.\n\n3. The one permutation variant C-MinHash-($\\pi$,$\\pi$) is practically interesting, which can use a single permutation to achieve very similar results as C-MinHash-($\\sigma$,$\\pi$).\n\n4. Extensive experiments justify their theoretical analysis over MinHash.\n\nCons:\n1. As claimed in the conclusion section, there exist other works improving MinHash with much fewer permutations, such as [1,2,4,6]. Thus, it will be more convincing to show more baselines in the numerical experiments in Section 4 rather than using MinHash only. \n\n2. Many important related works about MinHash are missing, such as [1-6]. I suggest the authors discuss more related works and illustrate their difference to C-MinHash.\n\nReference:\n\n[1] Li, Ping, Art Owen, and Cun-hui Zhang. \"One Permutation Hashing.\" Advances in Neural Information Processing Systems 25 (2012): 3113-3121.\n\n[2] Shrivastava, Anshumali, and Ping Li. \"Densifying one permutation hashing via rotation for fast near neighbor search.\" In International Conference on Machine Learning, pp. 557-565. PMLR, 2014.\n\n[3] Shrivastava, Anshumali, and Ping Li. \"Improved densification of one permutation hashing.\" In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, pp. 732-741. 2014.\n \n[4] Shrivastava, Anshumali. \"Optimal densification for fast and accurate minwise hashing.\" In International Conference on Machine Learning, pp. 3154-3163. PMLR, 2017.\n\n[5] Li, Ping, Xiaoyun Li, and Cun Hui Zhang. \"Re-randomized densification for one permutation hashing and bin-wise consistent weighted sampling.\" Advances in Neural Information Processing Systems 32 (2019).\n\n[6] Jia, Peng, Pinghui Wang, Junzhou Zhao, Shuo Zhang, Yiyan Qi, Min Hu, Chao Deng, and Xiaohong Guan. \"Bidirectionally Densifying LSH Sketches with Empty Bins.\" In Proceedings of the 2021 International Conference on Management of Data, pp. 830-842. 2021.", "summary_of_the_paper": "Min-wise hashing (MinHash) is a fundamental and popular algorithm in machine learning. This paper proposes Circulant MinHash (C-MinHash) to approximate the Jaccard similarity in massive binary data. Compared with MinHash, C-MinHash only requires two (or maybe one in practice) random permutations in a circulant manner for approximation. The authors also systematically demonstrate that the C-MinHash can provide a smaller estimation variance than MinHash. Extensive experiments validate the effectiveness of C-MinHash. \n\n", "summary_of_the_review": "Overall, the idea of this paper looks very promising, and the authors also achieve better theoretical results in terms of lower Jaccard estimation variance. However, the experiments and the related work are a lit weak. Such limitations justify my initial rating.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZaRxTwziZ8", "reviewer": "Reviewer_5hPp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Basically, I like the paper's motivation; it is quite a fundamental research problem to approximate the Jaccard similarity for large-scale data efficiently. Besides, this paper is well structured, and the theoretical background of the proposed approach is well described in the paper. Specifically, I really appreciate that this paper conducted an excellent job revealing the proposed approach's theoretical approximation quality. Furthermore, it experimentally confirms that the experimental results follow the theoretical results. \n\nHowever, I am concerned about the experiment since the paper compares the proposed approach to only the original approach of MinHash. Since MinHash is a popular approach with a long history, many variant approaches have been proposed below. Therefore, it needs to compare the proposed approach to the previous approach to demonstrate its usefulness.\n\n- Li et al., b-Bit Minwise Hashing for Estimating Three-Way Similarities\n- Ioffe, Improved Consistent Sampling, Weighted Minhash and L1 Sketching\n- Manasse et al., Consistent weighted sampling\n- Shrivastava, Exact Weighted Minwise Hashing in Constant Time", "summary_of_the_paper": "This paper proposes an effective approach for MinHash by permutating data vectors. It first randomly shuffles the data to break structures exhibited in the original data and then performs permutation K-times to obtain K hash values. Besides, this paper proposes an approach that performs only one permutation to compute hash values. This paper shows the theoretical approximation error of the proposed approach. By using text and image datasets, it shows that experimental results follow the results of the theoretical analysis.", "summary_of_the_review": "This paper is well-written.\nIt needs to compare the proposed approach to the previous approaches. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This was a somewhat unusual submission in that the authors tried to motivate their paper by pointing to a separate anonymous manuscript.  However, the authors didn't seem to want to confirm they would merge the manuscripts when asked about this. It was thought that in fairness the submitted manuscript should be judged on its own. After discussion, it was agreed that the submitted paper on its own, did not generate enough enthusiasm to merit acceptance.
Decision: Reject