summaries: 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.

summaries: The paper designs an improved version of the classical MinHash data structure for calculating the Jaccard similarity between two binary strings.  The 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.  This 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.

summaries: 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.

summaries: 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.

abstractText: 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 Circulant MinHash (C-MinHash) and provide the surprising theoretical results that using only 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.

authors:
Michael Bendersky
W. Bruce Croft

title: Finding text reuse on the web

authors:
Andrei Z. Broder
Steven C. Glassman
Mark S. Manasse
Geoffrey Zweig

title: Syntactic clustering of the web

venue: Comput. Networks,

authors:
Andrei Z. Broder
Moses Charikar
Alan M. Frieze
Michael Mitzenmacher

title: Min-wise independent permutations

authors:
Gregory Buehrer
Kumar Chellapilla

authors:
Flavio Chierichetti
Ravi Kumar
Silvio Lattanzi
Michael Mitzenmacher
Alessandro Panconesi
Prabhakar Raghavan

title: On compressing social networks

authors:
Ondrej Chum
Jiri Matas

authors:
Abhinandan Das
Mayur Datar
Ashutosh Garg
Shyamsundar Rajaram

authors:
Fan Deng
Stefan Siersdorfer
Sergej Zerr

authors:
Dheeru Dua
Casey Graff

title: UCI machine learning repository, 2017

venue: URL http://archive. ics.uci.edu/ml

authors:
Dennis Fetterly
Mark Manasse
Marc Najork
Janet L. Wiener

authors:
Derek Greene
Padraig Cunningham

authors:
Kaiming He
Fang Wen
Jian Sun

authors:
Piotr Indyk
Rajeev Motwani

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

venue: Proceedings of the IEEE,

authors:
David C. Lee
Qifa Ke
Michael Isard

authors:
Ping Li
Kenneth Ward Church

title: Using sketches to estimate associations

authors:
Ping Li
Arnd Christian König

venue: Commun. ACM,

authors:
Ping Li
Anshumali Shrivastava
Joshua Moore
Arnd Christian König

authors:
Ping Li
Art B Owen
Cun-Hui Zhang

title: One permutation hashing

authors:
Anshumali Shrivastava
Ping Li

title: In defense of minhash over simhash

authors:
Acar Tamersoy
Kevin A. Roundy
Duen Horng Chau

authors:
Felix X. Yu
Aditya Bhaskara
Sanjiv Kumar
Yunchao Gong
Shih-Fu Chang

venue: J. Mach. Learn. Res.,

authors:
Juan Zamora
Marcelo Mendoza
Héctor Allende

venue: Expert Syst. Appl.,

text:
1 INTRODUCTION
Given two D-dimensional binary vectors v,w ∈ {0, 1}D, the Jaccard similarity is defined as
J(v,w) = ∑D i=1 1{vi = wi = 1}∑D i=1 1{vi + wi ≥ 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 as the size of set intersection over the size of set union. The well-known method of “minwise hashing” (MinHash) (Broder, 1997; Broder et al., 1997; 1998; Li & Church, 2005; Li & König, 2011) is a standard technique for computing/estimating 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; Buehrer & Chellapilla, 2008; Bendersky & Croft, 2009; Chierichetti et al., 2009; Lee et 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 et al., 2016).
1.1 A REVIEW OF MINWISE HASHING (MINHASH)
Algorithm 1 Minwise-hashing (MinHash) Input: Binary data vector v ∈ {0, 1}D, K independent permutations π1, ..., πK : [D]→ [D].
Output: K hash values h1(v), ..., hK(v). For k = 1 to K
hk(v)← mini:vi 6=0 πk(i) End For
For simplicity, Algorithm 1 considers just one vector v ∈ {0, 1}D. In order to generate K hash values for v, we assume K independent permutations: π1, ..., πK : [D] 7→ [D]. For each permutation, the hash value is the first non-zero location in the permuted vector, i.e., hk(v) = mini:vi 6=0 πk(i), ∀k = 1, ...,K. Similarly, for another binary vector w ∈ {0, 1}D, using the same K permutations, we can also obtain K hash values, hk(w). The estimator of J(v,w) is simply
ĴMH(v,w) = 1
K K∑ k=1 1{hk(v) = hk(w)}, (2)
where 1{·} is the indicator function. By fundamental probability and the independence among the permutations, it is easy to show that
E[ĴMH ] = J, V ar[ĴMH ] = J(1− J)
K . (3)
How large is K? The answer depends on the application domains. For example, for training largescale 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 was that the hashed values did not form a metric space (e.g., satisfying the triangle inequality) and hence could not be used in many algorithms/applications. We believe this was the main reason why the original authors moved to using K permutations (Broder et al., 1998).
1.2 OUTLINE OF MAIN RESULTS
From K Permutations to two. The main idea of this work, is to replace the independent permutations in MinHash with “circulant” permutations. Thus, we name the proposed framework CMinHash (circulant MinHash). The “circulant” trick was used in the literature of random projections. 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 (estimation variances) are even more accurate. Basically, with the initial permutation (denoted by σ), we 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-(σ, π). Before that, in Section 2, we analyze a simpler variant C-MinHash-(0, π) without initial permutation σ. Although it is not our recommended method, our analysis for C-MinHash-(0, π) 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(π, π), that only needs one permutation π for both pre-processing and hashing. Although the theoretical analysis becomes very complicated, we are able to explicitly write down the expectation of the estimator, which is no longer unbiased but the bias is extremely small and has essentially no impact on the estimation accuracy (mean square errors). Extensive experiments are provided to verify that this variant has same estimation accuracy as C-MinHash-(σ, π) 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 a tool to improve more MinHash based algorithms, for example, the One Permutation Hashing (OPH, Li et al. (2012)). When combined with OPH, CMinHash can reduce the required one permutation to effectively 1/K permutation only. Since such combination is a research direction which requires independent introduction and efforts, we present the work in a separate manuscript (which could be anonymously shared with Referees if needed).
Algorithm 2 C-MinHash-(0, π) Input: Binary data vector v ∈ {0, 1}D, Permutation vector π: [D]→ [D] Output: Hash values h1(v), ..., hK(v)
For k = 1 to K Shift π circulantly rightwards by k units: πk = π→k hk(v)← mini:vi 6=0 π→k(i)
2 C-MINHASH-(0, π) WITHOUT INITIAL PERMUTATION
As shown in Algorithm 2, the C-MinHash algorithm has similar operations as MinHash. The difference lies in the permutations used in the hashing process. To generate each hash hk(v), we permute the data vector using π→k, which is the permutation shifted k units circulantly towards right based on π. For example, π = [3, 1, 2, 4], π→1 = [4, 3, 1, 2], π→2 = [2, 4, 3, 1], etc. Conceptually, we may think of circulation as concatenating the first and last elements of a vector to form a circle; see Figure 1. We set the hash value hk(v) as the position of the first non-zero after being permuted by π→k. Analogously, we define the C-MinHash-(0, π) estimator of the Jaccard similarity J(v,w) as
Ĵ0,π = 1
K K∑ k=1 1{hk(v) = hk(w)}, (4)
where h is the hash value output by Algorithm 2. In this paper, for simplicity, we assume K ≤ D. Next, we present the theoretical analysis for Algorithm 2, in terms of the expectation (mean) and the variance of the estimator Ĵ0,π . 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, we introduce some notations and definitions. Given v,w ∈ {0, 1}D, we define a and f as
a = D∑ i=1 1{vi = 1 and wi = 1}, f = D∑ i=1 1{vi = 1 or wi = 1}. (5)
We say that (v,w) is a (D, f, a)-data pair, whose Jaccard similarity can also be written as J = a/f . Definition 2.1. Consider v,w ∈ {0, 1}D. Define the location vector as x ∈ {O,×,−}D, with xi being “O”, “×”, “−”, when vi = wi = 1, vi + wi = 1 and vi = wi = 0, respectively.
The location vector x can fully characterize a hash collision. When a permutation π→k is applied, the hashes hk(v) and hk(w) would collide if after permutation, the first “O” is placed before the first “×” (counting from small to large). This observation will be the key in our theoretical analysis.
Definition 2.2. For A,B ∈ {O,×,−}, let {(A,B)|4} denote the set {(i, j) : (xi,xj) = (A,B), j − i = 4}. For each 1 ≤ 4 ≤ K − 1, define
L0(4) = {(O,O)|4}, L1(4) = {(O,×)}, L2(4) = {(O,−)}, G0(4) = {(−, O)|4}, G1(4) = {(−,×)} ,G2(4) = {(−,−)}, H0(4) = {(×, O)|4}, H1(4) = {(×,×)}, H2(4) = {(×,−)}.
Remark 2.1. For the ease of notation, by circulation we write xj = xj−D when D < j < 2D.
Definition 2.2 measures the relative location of different types of points in the location vector, for a specific pair of data vectors. One can easily verify that for ∀1 ≤ 4 ≤ K − 1,
|L0|+ |L1|+ |L2| = |L0|+ |G0|+ |H0| = a, |G0|+ |G1|+ |G2| = |L2|+ |G2|+ |H2| = D − f, |H0|+ |H1|+ |H2| = |L1|+ |G1|+ |H1| = f − a,
(6)
which is the intrinsic constraints on the size of above sets. We are now ready to analyze the expectation and variance of Ĵ0,π . It is easy to see that Ĵ0,π is still unbiased, i.e., E[Ĵ0,π] = J , by linearity of expectation. Lemma 2.1 provides an important quantity that leads to V ar[Ĵ0,π] as in Theorem 2.2. Lemma 2.1. For any 1 ≤ s < t ≤ K with t− s = 4, we have
Eπ [ 1{hs(v) = hs(w)}1{ht(v) = ht(w)} ] = |L0(4)|+ (|G0(4)|+ |L2(4)|)J
f + |G0(4)|+ |G1(4)| ,
where the sets are defined in Definition 2.2 and hs, ht are the hash values as in Algorithm 2.
Theorem 2.2. Under the same setting as in Lemma 2.1, the variance of Ĵ0,π is
V ar[Ĵ0,π] = J
K +
2 ∑K s=2(s− 1)ΘK−s+1
K2 − J2, where Θ4 , Eπ [ 1{hs(v) = hs(w)}1{ht(v) = ht(w)} ] as in Lemma 2.1 with any t− s = 4.
From Theorem 2.2, we see that the variance of Ĵ0,π 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 x. Since we use the original data vectors without randomly permuting the entries beforehand, V ar[Ĵ0,π] is called “locationdependent” as it is dependent on the location of non-zero entries of the original data.
3 C-MINHASH-(σ, π) WITH INDEPENDENT INITIAL PERMUTATION
Algorithm 3 C-MinHash-(σ, π) Input: Binary data vector v ∈ {0, 1}D, Permutation vectors π and σ: [D]→ [D] Output: Hash values h1(v), ..., hK(v)
Initial permutation: v′ = σ(v) For k = 1 to K
Shift π circulantly rightwards by k units: πk = π→k hk(v)← mini:v′i 6=0 π→k(i)
End For
The method C-MinHash-(σ, π) is summarized in Algorithm 3, which is very similar to Algorithm 2. This time, as pre-processing, we apply an initial permutation σ |= π on the data to break whatever structures which might exist. Similarly, we define the C-MinHash-(σ, π) estimator of J as
Ĵσ,π = 1
K K∑ k=1 1{hk(v) = hk(w)}, (7)
where hk’s are the hash values output by Algorithm 3. We will present our detailed theoretical analysis and the main result (Theorem 3.5). First, by linearity of expectation and that σ and π are independent, Ĵσ,π is still an unbiased estimator E[Ĵσ,π] = E[1{hi(v) = hi(w)}] = J . To provide 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.
Proposition 3.1. In (7), Cov(1{hi(v) = hi(w)},1{hj(v) = hj(w)}) < 0, ∀i 6= j.
Proof. Denote Ẽ = Ei 6=j [1{hi(v) = hi(w)}1{hj(v) = hj(w)}], for i 6= j. The task is then to show that Cov(1{hi(v) = hi(w)},1{hj(v) = hj(w)}) = Ẽ − J2 < 0. By Theorem 3.5, V ar[ĴMH ] < V ar[Ĵσ,π], where V ar[ĴMH ] = J(1−J) K and
V ar[Ĵσ,π] = E [( Ĵσ,π )2] − J2 = E ( 1 K K∑ k=1 1{hk(v) = hk(w)} )2− J2 = ∑ i E[1{hi(v) = hi(w)}]
K2 +
∑ i 6=j E[1{hi(v) = hi(w)}1{hj(v) = hj(w)}]
K2 − J2
= J K + K(K − 1)E[1{hi(v) = hi(w)}1{hj(v) = hj(w)}] K2 − J2, where i 6= j
= J
K + (K − 1)Ẽ K − J2 < J(1− J) K
=⇒ ( Ẽ − J2 )( 1− 1
K
) < 0 =⇒ Ẽ − J2 < 0.
Next, we formally present the path to our main result. The next Theorem gives the variance of Ĵσ,π . Theorem 3.2. Let a, f be defined as in (5). When 0 < a < f ≤ D (J /∈ {0, 1}), we have
V ar[Ĵσ,π] = J
K + (K − 1)Ẽ K − J2, (8)
where with l = max(0, D − 2f + a), and
Ẽ =Ei 6=j [1{hi(v) = hi(w)}1{hj(v) = hj(w)}] = ∑
{l0,l2,g0,g1}
{( l0
f + g0 + g1 +
a(g0 + l2)
(f + g0 + g1)f
)
× D−f−1∑ s=l ( D−f s )( D−a−1 D−f−1 ) ( f−a−1D−f−s−1)( sn1)(D−f−sn2 )(D−f−sn3 )(f−a−(D−f−s)n4 )( a−1a−l1−l2)( D−1 a ) }. (9) The feasible set {l0, l2, g0, g1} satisfies the intrinsic constraints (6), and
n1 = g0 − (D − f − s− g1), n2 = D − f − s− g1, n3 = l2 − g0 + (D − f − s− g1), n4 = l1 − (D − f − s− g1).
Also, when a = 0 or f = a (J = 0 or J = 1), we have V ar[Ĵσ,π] = 0.
Since the original locational structure of the data is broken by the initial permutation σ, V ar[Ĵσ,π] only depends on the value of (D, f, a), i.e., it is “location-independent”. This would make the performance of C-MinHash-(σ, π) consistent in different tasks. Same as MinHash, Proposition 3.3 states that givenD and f , the variance of Ĵσ,π is symmetric about J = 0.5, as illustrated in Figure 2, which also shows that the variance of Ĵσ,π is smaller than the variance of the original MinHash.
Proposition 3.3 (Symmetry). V ar[Ĵσ,π] is the same for the (D, f, a)-data pair and the (D, f, f − a)-data pair, ∀0 ≤ a ≤ f ≤ D.
V ar[Ĵσ,π ]
, D = 1000, K = 800. Right: Variance ratio V ar[ĴMH ]
V ar[Ĵσ,π ]
, D = 1000.
A rigorous comparison of V ar[Ĵσ,π] and V ar[ĴMH ] appears to be a challenging task given the complicated combinatorial form of V ar[Ĵσ,π]. The following lemma characterizes an important property of Ẽ in (9), that it is monotone in D when a and f are fixed, as illustrated in Figure 3 (left). Lemma 3.4 (Increasing Increment). Assume f > a > 0 are arbitrary and fixed. Denote ẼD as in (9) in Theorem 3.2, with D treated as a parameter. Then we have ẼD+1 > ẼD for ∀D ≥ f .
Equipped with Lemma 3.4, we arrive at the following main theoretical result of this work, on the uniform variance reduction of C-MinHash-(σ, π). Theorem 3.5 (Uniform Superiority). For any two binary vectors v,w ∈ {0, 1}D with J 6= 0 or 1, it holds that V ar[Ĵσ,π(v,w)] < V ar[ĴMH(v,w)].
That is, using merely two permutations as C-MinHash-(σ, π) improves the Jaccard estimation variance of classical MinHash, in all cases. Next, in Figure 3 (mid) and Theorem 3.6, we 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 V ar[ĴMH(v,w)]
V ar[Ĵσ,π(v,w)] is constant for any 0 < a < f .
How is the improvement affected by the sparsity (i.e., f ) and the number of hashes K? In Figure 3 (right), we plot the variance ratio V ar[ĴMH ]
V ar[Ĵσ,π] with different f and K, given fixed D. We see that the
improvement in 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 a which does not affect the variance ratio. The results in Figure 3 again verify Theorem 3.5, as the variance ratio is always greater than 1.
4 NUMERICAL EXPERIMENTS
In this section, we provide numerical experiments to validate our theoretical findings and demonstrate that C-MinHash can indeed lead to smaller Jaccard estimation errors.
4.1 SANITY CHECK: A SIMULATION STUDY
A simulation study is conducted on synthetic data to verify the theoretical variances given by Theorem 2.2 and Theorem 3.2. We simulate D = 128 dimensional binary vector pairs (v,w) with different f and a, which have a special locational structure that the location vector x is such that a “O”’s are followed by (f − a) “×”’s and then followed by (D− f) “−”’s sequentially. We plot the empirical and theoretical mean square errors (MSE = variance + bias2) in Figure 4:
• The theoretical variance agrees with the empirical observation, as the curves overlap, confirming Theorem 2.2 and Theorem 3.2. The variance reduction increases with larger K.
• V ar[Ĵσ,π] (C-MinHash-(σ, π)) is always smaller than V ar[ĴMH ], as stated by Theorem 3.5. In contrast, V ar[Ĵ0,π] (C-MinHash-(0, π)) varies significantly depending on different data structures, as mentioned in Section 2.
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(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-(σ, π) is consistently smaller than that of MinHash, again confirming Theorem 3.5 on 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 σ, the accuracy of C-MinHash-(0, π) is affected by the distribution of the original data, and it is worse than C-MinHash-(σ, π) on all these four datasets. Also, the performance of C-MinHash-(0, π) on image data seems much worse than that on text data, which we believe is because the image datasets contain more structural patterns. This again suggests that the initial permutation σ might be needed in practice.
In summary, the simulation study has verified the correctness of our theoretical findings in Theorem 2.2 and Theorem 3.2. The experiments with Jaccard estimation on four datasets confirm that C-MinHash is more accurate than the original MinHash. The initial permutation σ is recommended.
5 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-processing and circulant hashing. The procedure is the same as Algorithm 3, except that the initial permutation σ is replaced by π. Denote the Jaccard estimator Ĵπ,π .
The complicated dependency between π (initial permutation) and π→k (hashing) makes the theoretical analysis challenging. In the following, we provide the mean of each hash collision indicator. Theorem 5.1. Assume K ≤ D and let a, f be defined as (5). The location vector x is defined in Definition 2.1. Denote B1 = {i : xi = O}, B2 = {i : xi = ×} and B3 = {i : xi = −}. For a ≤ j ≤ D and 1 ≤ k ≤ K, define
A−(j) = {xi : (i+ k − 1 mod D) + 1 ≤ j}, A+(j) = {xi : (i+ k − 1 mod D) + 1 > j}.
Let n−,1(j) = |{xi = O : i ∈ A−(j)}| be the number of “O” points in A−(j). Analogously let n−,2(j), n−,3(j) be the number of “×” and “−” points in A−(j), and n+,1(j), n+,2(j), n+,3(j) be the number of “O”, “×” and “−” points in A+(j). Then, for the k-th C-MinHash-(π, π) hash,
E[1{hk(v) = hk(w)}] = D∑ j=1 ∑ Z∈Θj Pj(Z) · { 3∑ i=1 Ψi(j) + ∑ i∈B1 (1− z−,1 n−,1(i∗) )P̃1 } ,
where Pj(Z) is the density function of Z = (z−,k|31, z+,k|31) which follows hyper(D,D − f, n−,k(j)|31, n+,k(j)|31), with domain Θj . For q = 1, 2, 3, denote 1#q = 1{j# ∈ Bq}, and Ψq(j) = ∑
i∈Bq,j<i∗ 3∑ p=1 1 # p ( 1− z−,p n−,p(j) + 1{q = 3}(2 z−,p n−,p(j) − 1) ) (1− z+,q n+,q(j) )P̃qJ̄q
+ ∑
i∈Bq,j>i∗
[ 1
# q (1− z−,q n−,q(j) )(1− z−,q n−,q(j)− 1 ) + 3∑ p 6=q 1 # p (1− z−,q n−,q(j) )(1− z−,p n−,p(j) ) ] P̃qJ ∗,
where i∗ = (i+ k − 1 mod D) + 1, i# = (i− k − 1 mod D) + 1, ∀i. Define J∗ = a−r1f−r1−r2 , and
P̃1 = P̃2 = 1
r1 + r2
( b0 r3 )( D−j−b0 r1+r2−1 )( D−f r3 )( f r1+r2 ) , P̃3 = 1 r3 ( b0 r3−1 )( D−j−b0 r1+r2 )( D−f r3 )( f r1+r2
) , J̄q =
r1 − 1{q = 1} D − j − b0 + (1− r1 + r2 − 1{q 6= 3} D − j − b0 )J∗, q = 1, 2, 3,
where b0 = ∑3 k=1 z+,k, r1 = a−z−,1−z+,1, r2 = f−a−z−,2−z+,2 and r3 = D−f−z−,3−z+,3.
Theorem 5.1 says that E[1{hk(v) = hk(w)}] would be different for different k. Figure 6 presents numerical examples to validate the theory and demonstrate the magnitude of bias2 (recall MSE = bias2 + variance), where the simulations match perfectly Theorem 5.1. As the bias of E[1{hk(v) =
hk(w)}] can be positive or negative, the overall bias of Ĵπ,π would approach 0 asK increases. From the 2nd row, we see that bias2 is very small (10−5 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, E[Ĵπ,π] would converge to J .
We found through extensive numerical experiments that, the MSE of Ĵπ,π is essentially the same as Ĵσ,π . Figure 7 (1st row) compares the empirical of C-MinHash-(π, π) with the theoretical variances of C-MinHash-(σ, π), where the simulated data has the same special locational structure as in Section 4.1. In the 2nd row, we present the MAE comparison on real datasets, where we see that the curves for these two estimators (Ĵσ,π 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.
6 CONCLUSION
The method of minwise hashing (MinHash), from the seminal works of Broder and his colleagues, has become standard in industrial practice. One fundamental reason for its wide applicability is that the binary (0/1) high-dimensional 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 permutations, 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 a circulant shifting fashion. Moreover, we analyze a more convenient C-MinHash variance which uses only 1 permutation for both pre-processing 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 unrealistic to store (e.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, we mention that our work can be used as a building block to improve Li et al. (2012), reducing the required one permutation to effectively 1/K permutation only. If needed, we would be happy to anonymously share the technical manuscript with the related results.
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 Conference 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):1157–1166, 1997.
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. Min-wise independent permutations. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC), pp. 327–336, Dallas, TX, 1998.
Gregory Buehrer and Kumar Chellapilla. A scalable pattern mining approach to web graph compression 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 on 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 on Computer Vision and Pattern Recognition (CVPR), pp. 3077–3084, Providence, RI, 2012.
Abhinandan Das, Mayur Datar, Ashutosh Garg, and Shyamsundar Rajaram. Google news personalization: scalable online collaborative filtering. In Proceedings of the 16th International Conference on World Wide Web (WWW), pp. 271–280, Banff, Alberta, Canada, 2007.
Fan Deng, Stefan Siersdorfer, and Sergej Zerr. Efficient jaccard-based diversity analysis of large document collections. In 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://archive. ics.uci.edu/ml.
Dennis Fetterly, Mark Manasse, Marc 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 affinity-preserving 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: a large-scale evaluation of algorithms. In Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), pp. 284–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.
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(11):2278–2324, 1998.
David C. Lee, Qifa Ke, and Michael Isard. Partition min-hash 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 (HLT/EMNLP), pp. 708–715, Vancouver, Canada, 2005.
Ping Li and Arnd Christian König. Theory and applications of b-bit minwise hashing. Commun. ACM, 54(8):101–109, 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 of 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 on 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 embedding using circulant matrices. J. Mach. Learn. Res., 18:150:1–150:30, 2017.
Juan Zamora, Marcelo Mendoza, and Héctor Allende. Hashing-based clustering in high dimensional data. Expert Syst. Appl., 62:202–211, 2016.
A PROOFS OF TECHNICAL RESULTS
Notations. In our analysis, we will use 1s to denote 1{hs(v) = hs(w)} in for ∀1 ≤ s ≤ K, where h is the hash value. Given two data vectors v,w ∈ {0, 1}D. Recall in (5): a = ∑D i=1 1{vi =
1 and wi = 1}, f = ∑D i=1 1{vi = 1 or wi = 1}. Thus, the Jaccard similarity J = a/f . We also define J̃ = (a− 1)/(f − 1).
Definition A.1. Let v,w ∈ {0, 1}D. Define the location vector as x ∈ {O,×,−}D, with xi being “O”, “×”, “−” when vi = wi = 1, vi + wi = 1 and vi = wi = 0, respectively.
Definition A.2. For A,B ∈ {O,×,−}, let {(i, j) : (A,B)|4} denote a pair of indices {(i, j) : (xi,xj) = (A,B), j − i = 4}. Define L0(4) = {(i, j) : (O,O)|4}, L1(4) = {(i, j) : (O,×)|4}, L2(4) = {(i, j) : (O,−)|4}, G0(4) = {(i, j) : (−, O)|4}, G1(4) = {(i, j) : (−,×)|4} ,G2(4) = {(i, j) : (−,−)|4}, H0(4) = {(i, j) : (×, O)|4}, H1(4) = {(i, j) : (×,×)|4}, H2(4) = {(i, j) : (×,−)|4}.
Remark A.1. For the ease of notation, by circulation we write xj = xj−D when D < j < 2D.
One can easily verify that given fixed a, f,D, it holds that for ∀1 ≤ 4 ≤ K − 1, |L0(4)|+ |L1(4)|+ |L2(4)| = |L0(4)|+ |G0(4)|+ |H0(4)| = a, |G0(4)|+ |G1(4)|+ |G2(4)| = |L2(4)|+ |G2(4)|+ |H2(4)| = D − f, |H0(4)|+ |H1(4)|+ |H2(4)| = |L1(4)|+ |G1(4)|+ |H1(4)| = f − a.
(10)
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 1 ≤ s < t ≤ K with t− s = 4, we have
Eπ [ 1{hs(v) = hs(w)}1{ht(v) = ht(w)} ] = |L0(4)|+ (|G0(4)|+ |L2(4)|)J
f + |G0(4)|+ |G1(4)| ,
where the sets are defined in Definition 2.2 and hs, ht are the hash values as in Algorithm 2.
Proof. To check whether a hash sample generated by MinHash collides (under some permutation π), it suffices to look at the permuted location vector x. If a collision happens, after permuted by π, type “O” point must appear before the first “×” point. That said, the minimal permutation index of “O” elements must be smaller than that of “×” elements. If the hash sample does not collide, then the first “×” must appear before the first “O”. Note that “−” points does not affect the collision. To compute the variance of the estimator, it suffices to compute E[1s1t]. Let L, G and H be the union of L’s, G’s and H’s, respectively. In the following, we say that an index i belongs to a set if i is the first term of an element in that set. We have
|L| = a, |H| = f − a, |G| = D − f. One key observation is that, for a pair (i, j) in above sets, the hash index πs(i) will be the hash index of πt(j). We begin by decomposing the expectation into
E[1s1t] = P [collision s, collision t] = ∑ i∗s∈L P [collision s at i∗s, collision t]
= 2∑ p=0 ∑ i∗s∈Lp P [collision s at i∗s, collision t]. (11)
where i∗s 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 x(πs). Note that the permutation is totally random, so the location of collision is independent of 1s, and uniformly distributed among all type “O” pairs.
1) When i∗s ∈ L0. In this case, the minimum index of the type “O” pair in x(πs), πs(i∗s), is shifted to another type “O” pair in x(πt). Therefore, the indices of pairs with the first element being “O” or “×” originally in x(πs) will still be greater than πt(i∗s). If sample s collides at i∗s , hash sample t will collide when
1. All the points in G1, after permutation πs, is greater than πs(i∗s). In this case, regardless of the permuted G0, hash t will always collide.
2. There exist points in G1 after permutation πs smaller than πs(i∗s), and also points in G0 that is smaller than the minimum of permuted G1.
Consequently, we have for i∗s ∈ L0,
P [collision s at i∗s, collision t] = P [πs(i ∗ s) < πs(i),∀i ∈ H ∪ L/i∗s, and min
j∈G1 πs(j) > πs(i
∗ s)]
+ P [πs(i ∗ s) < πs(i),∀i ∈ H ∪ L/i∗s, and min
j∈G0 πs(j) < min j∈G1 πs(j) < πs(i
∗ s)]
= 1 a · a f + |G1| + |G0| f + |G0|+ |G1| · |G1| f + |G1| · a f · 1 a
= 1
f + |G1| + |G0| · |G1| (f + |G0|+ |G1|)(f + |G1|)f . (12)
This probability holds for ∀i∗s ∈ L0.
2) When i∗s ∈ L1. Similarly, we consider the condition where i∗s ∈ L1, and both hash samples collide. In this case, πs(i∗s) would be shifted to a “×” pair in x(πt). That is, the indices of pairs with the first element being “O” or “×” originally in x(πs) will all become greater than πs(i∗s), which now is the location of a “×” pair in x(πt). Thus, to make hash t collide, we will need:
• At least one point from G0 is smaller than any other points inH∪L∪G1 after permutation πs.
Therefore, for any i∗s ∈ L1,
P [collision s at i∗s, collision t] = P [πs(i ∗ s) < πs(i),∀i ∈ H ∪ L/i∗s, and min
j∈G0 πs(j) < min{πs(i∗s),min j∈G1 πs(j)}]
= |G0| f + |G0|+ |G1| · a f · 1 a
= |G0|
(f + |G0|+ |G1|)f , (13)
which is true for ∀i∗s ∈ L1.
3) When i∗s ∈ L2. In this scenario, πs(i∗s) would be shifted to a “−” pair in x(πt). Therefore, if hash s collides, hash t will also collide when:
• After applying πs, the minimum of L0 ∪ H0 ∪ G0 is smaller than the minimum of L1 ∪ H1 ∪ G1.
Thus, we obtain that for any i∗s ∈ L2,
P [collision s at i∗s, collision t] = P [πs(i ∗ s) < πs(i),∀i ∈ H ∪ L/i∗s, and min
j∈L0∪G0∪H0 πs(j) < min j∈L1∪G1∪H1 πs(j)]
, P [Ω].
Let 1s,i∗s denote the event {πs(i ∗ s) < πs(i),∀i ∈ H ∪ L/i∗s}. Then Ω can be separated into the following several cases:
1. Ω1: 1s,i∗s , minj∈L0∪H0 πs(j) < minj∈L1∪H1 πs(j), and minj∈L0∪H0 πs(j) < minj∈G1 πs(j).
2. Ω2: 1s,i∗s , minj∈L0∪H0 πs(j) < minj∈L1∪H1 πs(j), and minj∈L0∪H0 πs(j) > minj∈G1 πs(j) > minj∈G0 πs(j) > πs(i ∗ s).
3. Ω3: 1s,i∗s , minj∈L0∪H0 πs(j) < minj∈L1∪H1 πs(j), and minj∈L0∪H0 πs(j) > minj∈G1 πs(j) > πs(i ∗ s) > minj∈G0 πs(j).
4. Ω4: 1s,i∗s , minj∈L0∪H0 πs(j) < minj∈L1∪H1 πs(j), and minj∈L0∪H0 πs(j) > πs(i ∗ s) >
minj∈G1 πs(j) > minj∈G0 πs(j).
5. Ω5: 1s,i∗s , minj∈L0∪H0 πs(j) > minj∈L1∪H1 πs(j), and πs(i ∗ s) < minj∈G0 πs(j) <
minj∈L1∪H1∪G1 πs(j).
6. Ω6: 1s,i∗s , minj∈L0∪H0 πs(j) > minj∈L1∪H1 πs(j), and minj∈G0 πs(j) < πs(i ∗ s) <
minj∈L1∪H1∪G1 πs(j).
We can compute the probability of each event as
P [Ω1] = 1 a · a f + |G1| · |L0|+ |H0| |L0|+ |H0|+ |L1|+ |H1|+ |G1| ,
= a− |G0|
(f − |G0|)(f + |G1|) ,
P [Ω2] = 1 a · a f + |G0|+ |G1| · |G0| |G0|+ |G1|+ |L0|+ |H0|+ |L1|+ |H1|
· |G1| |L0|+ |H0|+ |L1|+ |H1|+ |G1| · |L0|+ |H0| |L0|+ |H0|+ |L1|+ |H1|
= 1 f + |G0|+ |G1| · |G0| f · |G1| f − |G0| · a− |G0| f − |G0| − |G1|
= |G0| · |G1| · (a− |G0|)
(f + |G0|+ |G1|)(f − |G0|)(f − |G0| − |G1|)f ,
P [Ω3] = |G0| f + |G0|+ |G1| · 1 f + |G1| · |G1| |L0|+ |H0|+ |L1|+ |H1|+ |G1| · |L0|+ |H0| |L0|+ |H0|+ |L1|+ |H1|
= |G0| · |G1| · (a− |G0|)
(f + |G0|+ |G1|)(f + |G1|)(f − |G0|)(f − |G0| − |G1|) ,
P [Ω4] = |G0| f + |G0|+ |G1| · |G1| f + |G1| · 1 f · |L0|+ |H0| |L0|+ |H0|+ |L1|+ |H1|
= |G0| · |G1| · (a− |G0|)
(f + |G0|+ |G1|)(f + |G1|)(f − |G0| − |G1|)f ,
P [Ω5] = 1 f + |G0|+ |G1| · |G0| |G0|+ |G1|+ |L0|+ |H0|+ |L1|+ |H1| · |L1|+ |H1| |L0|+ |H0|+ |L1|+ |H1|
= |G0| · (f − a− |G1|)
(f + |G0|+ |G1|)(f − |G0| − |G1|)f ,
P [Ω6] = |G0| f + |G0|+ |G1| · 1 f · |L1|+ |H1| |L0|+ |H0|+ |L1|+ |H1|
= |G0| · (f − a− |G1|)
(f + |G0|+ |G1|)(f − |G0| − |G1|)f .
Note that
P [Ω2] + P [Ω3] + P [Ω4]
= |G0| · |G1| · (a− |G0|)
(f + |G0|+ |G1|)(f − |G0| − |G1|)
[ 1
(f − |G0|)f +
1
(f − |G0|)(f + |G1|) +
1
f(f + |G1|) ] =
|G0| · |G1| · (a− |G0|)(3f − |G0|+ |G1|) (f + |G0|+ |G1|)(f − |G0| − |G1|)f(f − |G0|)(f + |G1|) .
Summing up all the terms together, we obtain P [Ω] as 6∑ n=1 P [Ωn] = f(f + |G0|+ |G1|)(f − |G0| − |G1|)(a− |G0|) + |G0||G1|(a− |G0|)(3f − |G0|+ |G1|) (f + |G0|+ |G1|)(f − |G0| − |G1|)(f − |G0|)(f + |G1|)f
+ 2|G0|(f − a− |G1|)(f − |G0|)(f + |G1|)
(f + |G0|+ |G1|)(f − |G0| − |G1|)(f − |G0|)(f + |G1|)f
= (a− |G0|)(f + |G0| − |G1|)(f − |G0|)(f + |G1|) + 2|G0|(f − a− |G1|)(f − |G0|)(f + |G1|)
(f + |G0|+ |G1|)(f − |G0| − |G1|)(f − |G0|)(f + |G1|)f
= (a+ |G0|)(f − |G0| − |G1|)(f − |G0|)(f + |G1|)
(f + |G0|+ |G1|)(f − |G0| − |G1|)(f − |G0|)(f + |G1|)f
= a+ |G0|
(f + |G0|+ |G1|)f , (14)
which holds for ∀i∗s ∈ L2. Now combining (12), (13), (14) with (11), we obtain
E[1s1t] = |L0|
f + |G1| + |G0||G1||L0| (f + |G0|+ |G1|)(f + |G1|)f + |G0||L1| (f + |G0|+ |G1|)f + (a+ |G0|)|L2| (f + |G0|+ |G1|)f .
(15)
Here, recall that the sets are associated with all 1 ≤ s < t ≤ K such that 4 = t − s. Using the intrinsic constraints (10), after some calculation we can simplify (15) as
Eπ[1s1t] = |L0|
f + |G0|+ |G1| + a(|G0|+ |L2|) (f + |G0|+ |G1|)f ,
which completes the proof.
A.2 PROOF OF THEOREM 2.2
Theorem 2.2. Under the same setting as in Lemma 2.1, the variance of Ĵ0,π is
V ar[Ĵ0,π] = J
K +
2 ∑K s=2(s− 1)ΘK−s+1
K2 − J2,
where Θ4 , Eπ [ 1{hs(v) = hs(w)}1{ht(v) = ht(w)} ] as in Lemma 2.1 with any t− s = 4.
Proof. By the expansion of variance formula, since E[12s] = E[1s] = J , we have
V ar[Ĵ0,π] = J
K +
∑K s=1 ∑K t 6=s E[1s1t] K2 − J2. (16)
Note here that for ∀t > s, the t-th hash sample uses πt as the permutation, which is shifted rightwards by 4 = t − s from πs. Thus, we have E[1s1t] = E[1s−i1t−i] for ∀0 < i < s ∧ t, which implies E[1s1t] = E[111t−s+1], ∀s < t. Since by assumption K ≤ D, we have K∑ s K∑ t 6=s E[1s1t] = 2E [ (1112 + 1113 + ...+ 111K) + (1213 + ...+ 121K) + ...+ 1K−11K
] = 2E [ (1112 + 1113 + ...+ 111K) + (1112 + ...+ 111K−1) + ...+ 1112 ]
= 2 K∑ s=2 (s− 1)E[111K−s+2]
, 2 K∑ s=2 (s− 1)ΘK−s+1. (17)
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 0 < a < f ≤ D (J /∈ {0, 1}), we have
V ar[Ĵσ,π] = J
K + (K − 1)Ẽ K − J2, (18)
where with l = max(0, D − 2f + a), and Ẽ = ∑
{l0,l2,g0,g1}
{( l0
f + g0 + g1 +
a(g0 + l2)
(f + g0 + g1)f
)
× D−f−1∑ s=l ( D−f s )( D−a−1 D−f−1 ) ( f−a−1D−f−s−1)( sn1)(D−f−sn2 )(D−f−sn3 )(f−a−(D−f−s)n4 )( a−1a−l1−l2)( D−1 a ) }. (19)
The feasible set {l0, l2, g0, g1} satisfies the intrinsic constraints (6), and
n1 = g0 − (D − f − s− g1), n2 = D − f − s− g1, n3 = l2 − g0 + (D − f − s− g1), n4 = l1 − (D − f − s− g1).
Also, when a = 0 or f = a (J = 0 or J = 1), we have V ar[Ĵσ,π] = 0.
Proof. Similar to the proof of Theorem 2.2, we denote Θ4 = Eσ,π[1s1t] with |t − s| = 4. Note that now the expectation is taken w.r.t. both two independent permutations σ and π. Since σ is random, we know that Θ1 = Θ2 = · · · = ΘK−1. Then by the variance formula, we have
V ar[Ĵσ,π] = J2 K − (K − 1)Θ1 K − J2 (20)
Hence, it suffices to consider Θ1. In this proof, we will set 4 = 1 and drop the notation 4 for conciseness, and denote Ẽ = Θ1 from now on. First, we note that Lemma 2.1 gives the desired quantity conditional on σ. By the law of total probability, we have
Ẽ = Eσ [
|L0| f + |G0|+ |G1| + a(|G0|+ |L2|) (f + |G0|+ |G1|)f
] , (21)
where the sizes of sets are random depending on the initial permutation σ (i.e. counted after permuting by σ). As a result, the problem turns into deriving the distribution of |L0|, |L1|, |L2|, |G0| and |G1| under random permutation σ, and then taking expectation of (21) with respect to this additional randomness.
When a = 0, we know that |L0| = |L2| = |G0| = 0, hence the expectation Ẽ is trivially 0. Thus, the V ar[Ĵσ,π] = 0. When f = a, |G1| = 0, and the constraint on the sets becomes
|L0|+ |G0| = |L0|+ |L2| = f, |L2|+ |G2| = |G0|+ |G2| = D − f.
Then (21) becomes
Ẽ = Eσ [ |L0|
f + |G0| + |G0|+ |L2| f + |G0|
]
= Eσ [ |L0|+ |G0|+ |L2|
f + |G0|
] ≡ 1.
Therefore, when f = a, we also have V ar[Ĵσ,π] = 0.
Next, we will consider the general case where 0 < a < f ≤ D. This can be considered as a combinatorial problem where we randomly arrange a type “O”, (f − a) type “×” and (D − f) type “−” points in a circle. We are interested in the distribution of the number of {O,O}, {O,×}, {O,−}, {−, O} and {−,×} pairs of consecutive points in clockwise direction. We consider this procedure in two steps, where we first place “×” and “−” points, and then place “O” points.
Step 1. Randomly place “×” and “−” points on the circle.
In this step, four types of pairs may appear: {−,−}, {−,×}, {×,×} and {×,−}. Denote C1, C2, C3 and C4 as the collections of above pairs. Since
|C1|+ |C4| = |C1|+ |C2| = D − f, |C2|+ |C3| = |C2|+ |C4| = f − a,
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 |C1|. First, placing (D − f) “−” points on a circle leads to (D−f) number of {−,−} pairs. This (D−f) elements can be regarded as the borders that split the circle into (D− f) bins. Now, we randomly throw (f −a) number of “×” points into these bins. If at least one “×” falls into one bin, then the number of {−,−} pairs (|C1|) would reduce by 1, while |C2| and |C4| would increase by 1. If z “×” points fall into one bin, then the number of {×,×} (|C3|) would increase by (z − 1). Notice that since s ≤ D − f and D − f − s ≤ f − a, we have max(0, D − 2f + a) ≤ s ≤ D − f . Consequently, for s in this range, we have
P { |C1| = s } = P { |C1| = s, |C3| = f − a− (D − f − s) } = ( D−f D−f−s )( f−a−1 D−f−s−1 )(
D−a−1 D−f−1 ) = ( D−f s )( f−a−1 D−f−s−1 )(
D−a−1 D−f−1 ) . (22) 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 at least one ball is ( n−1 m−1 ) . For |C1| = s, we need n = f − a (number of “×”) and m = |C2| = D − f − s. Moreover, the number of ways to place n balls in m distinct bins is ( n+m−1 m−1 ) . When counting the total number of possibilities, we have n = f − a and m = D − f . This gives the denominator. We notice that (22) is actually a hyper-geometric distribution.
Step 2. Randomly place “O” points on the circle.
We have the probability mass function P [Ψ] , P { |L1| = l1, |L2| = l2, |G0| = g0, |G1| = g1 } =
D−f−1∑ s=D−2f+a P { |L1| = l1, |L2| = l2, |G0| = g0, |G1| = g1 ∣∣∣|C1| = s}P{|C1| = s}. (23) Now it remains to compute the distribution conditional on |C1|. Here we drop |L0| because it is intrinsically determined by |L1| and |L2|. Again, given a placement of all “×” and “−” points, each consecutive pair can be regarded as a 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 “×” and “−” points on the circle with |C1| = s (and thus |C2| = |C3| = D − f − s and |C4| = f − a − (D − f − s) are also determined correspondingly). In the following, we count the number of “O” points that fall in Ci, i = 1, 2, 3, 4, to make the event Ψ happen. Note that
• When at least one “O” point falls into C1 (between {−,−}), |L2| and |G0| increase by 1.
• When at least one “O” point falls into C2 (between {−,×}), |L1| and |G0| increase by 1, while |G1| decreases by 1.
• When at least one “O” point falls into C3 (between {×,−}), |L2| increases by 1.
• When at least one “O” point falls into C4 (between {×,×}), |L1| increases by 1.
We denote the number of bins in Ci, i = 1, 2, 3, 4 that contain at least one “O” point as n1, n2, n3, n4, respectively. As a result of above reasoning, in the event Ψ, we have n1 + n3 = l2, n2 + n4 = l1, n1 + n2 = g0,
D − f − s− n2 = g1.
Solving the equations gives  n1 = g0 − (D − f − s− g1), n2 = D − f − s− g1, n3 = l2 − g0 + (D − f − s− g1), n4 = l1 − (D − f − s− g1).
Note that ∑4 i=1 ni = l1 + l2. Therefore, event Ψ is equivalent to randomly pick n1, n2, n3 and n4 bins in C1,...,C4, and then distribute a type “O” points in these (l1 + l2) bins such that each bin contains at least one “O”. Hence, we obtain P { |L1| = l1, |L2| = l2, |G0| = g0, |G1| = g1
∣∣∣|C1| = s} = ( sn1)(D−f−sn2 )(D−f−sn3 )(f−a−(D−f−s)n4 )( a−1l1+l2−1)( D−1 D−a−1
) = ( s n1 )( D−f−s n2 )( D−f−s n3 )( f−a−(D−f−s) n4 )( a−1 a−l1−l2
)( D−1 a
) , (24)
which is also multi-variate hyper-geometric distributed. Now combining (22), (23) and (24), we obtain the joint distribution of |L0|, |L1|, |L2|, |G0| and |G1| as
P { |L1| = l1, |L2| = l2, |G0| = g0, |G1| = g1 } =
D−f−1∑ s=max(0,D−2f+a)
( s n1 )( D−f−s n2 )( D−f−s n3 )( f−a−(D−f−s) n4 )( a−1 a−l1−l2 )( D−1 a ) · (D−fs )( f−a−1D−f−s−1)( D−a−1 D−f−1
) . (25) Now let Ξ be the feasible set of (l0, l1, g0, g1, g2) that satisfies the intrinsic constraints (10). The desired expectation w.r.t. both π and σ can thus be written as Ẽ = ∑
Ξ
( l0
f + g0 + g1 +
a(g0 + l2)
(f + g0 + g1)f ) · D−f−1∑
s=max(0,D−2f+a)
( s n1 )( D−f−s n2 )( D−f−s n3 )( f−a−(D−f−s) n4 )( a−1 a−l1−l2 )( D−1 a ) · (D−fs )( f−a−1D−f−s−1)( D−a−1 D−f−1 )  .
The desired result can then follows by (20).
A.4 PROOF OF PROPOSITION 3.3
Proposition 3.3 (Symmetry). V ar[Ĵσ,π] is the same for the (D, f, a)-data pair and the (D, f, f − a)-data pair, ∀0 ≤ a ≤ f ≤ D.
Proof. For fixed a, f,D, let Ẽ1 be the expectation defined in Theorem 3.2 for (v1,w1), and Ẽ2 be that for (v2,w2). From Theorem 3.2 we know that
Ẽ1 = E(l0,l2,g0,g1) [ l0 f + g0 + g1 + a(g0 + l2) (f + g0 + g1)f ] ,
where (l0, l2, g0, g1) follows the distribution of (|L0|, |L2|, |G0|, |G1|) associated with the location vector x1 of (v1,v2). For data pair (v2,w2), we can consider its location vector x2 as swapping the “O” and “×” entries of x1. Now we denote the size of the corresponding sets (Definition 2.2) of x2 as l′is, g ′ is, h ′ is, for i = 0, 1, 2. Since σ is applied before hashing, by symmetry there is a one-to-one correspondence between the two location vectors. More specifically, l′0 corresponds to h1, g′0 corresponds to g1, g ′ 1 corresponds to g0, and l ′ 2 corresponds to h2. Therefore, in probability we can write
Ẽ2 = E(l′0,l′2,g′0,g′1) [ l′0 f + g′0 + g ′ 1 + a(g′0 + l ′ 2) (f + g′0 + g ′ 1)f ] = E(h1,h2,g0,g1) [ h1 f + g0 + g1 + (f − a)(g1 + h2) (f + g0 + g1)f ] .
Consequently, we have
Ẽ1 − Ẽ2 = E(l0,l2,h1,h2,g0,g1) [ l0 − h1 f + g0 + g1 + a(g0 + l2)− (f − a)(g1 + h2) (f + g0 + g1)f ] .
In the sequel, the subscript of expectation is suppressed for conciseness. Exploiting the constraints (10), we deduce that h1 = (f − a) − l1 − g1, h2 = l0 + g0 + l1 + g1 − a and l0 + l1 = a − l2. Using these facts we obtain
Ẽ1 − Ẽ2 = E [ (l0 − (f − a) + l1 + g1)f + a(g0 + l2)− (f − a)(l0 + g0 + l1 + 2g1 − a)
(f + g0 + g1)f ] = E
[ (2a− f + g1 − l2)f + a(g0 + l2)− (f − a)(2g1 + g0 − l2) (f + g0 + g1)f ] = E
[2(f + g0 + g1)a− (f + g0 + g1)f (f + g0 + g1)f ] = 2J − 1.
Comparing the variances of Ĵσ,π(v1,w1) and Ĵσ,π(v2,w2), we derive
V ar[Ĵσ,π(v1,w1)]− V ar[Ĵσ,π(v2,w2)]
= ( J
K + (K − 1)Ẽ1 K − J2)− (1− J K + (K − 1)Ẽ2 K − (1− J)2)
= −K − 1 K (2J − 1) + K − 1 K (Ẽ1 − Ẽ2) = 0.
This completes the proof.
A.5 PROOF OF LEMMA 3.4
Lemma 3.4 (Increasing Increment). Assume a > 0 and f > a are arbitrary and fixed. Denote ẼD as in (19) in Theorem 3.2, with D treated as a parameter. Then we have ẼD+1 > ẼD for ∀D ≥ f .
Proof. Let the probability mass function (25) with a, f and dimension D be Pa,f,D(l0, l2, g0, g1). Conditional on l0, l2, g0, g1 with D elements, the possible values l′0, l ′ 2, g ′ 0, g ′ 1 when adding a “−” are
• g′0 = g0 + 1, l ′ 0 = l0, l ′ 2 = l2, g ′ 1 = g1. This is true when the new elements falls between a
pair of (×, O), with probability l1+l2−g0D .
• g′1 = g1 + 1, l ′ 0 = l0, l ′ 2 = l2, g ′ 0 = g0, when the new elements falls between a pair of
(×,×), with probability f−a−l1−g1D .
• g′1 = g1 + 1, l ′ 2 = l2 + 1, l ′ 0 = l0, g ′ 0 = g0, when the new elements falls between a pair of
(O,×), with probability l1D .
• l′0 = l0 − 1, l′2 = l2 + 1, g′0 = g0 + 1, g′1 = g1, when the new elements falls between a pair of (O,O), with probability l0D .
• All values unchanged, when the “−” falls between other types of pairs, with probability D−f+g0+g1
D .
Denote ΞD as the feasible set satisfying (10) with dimension D ≥ f . Above reasoning builds a correspondence between ΞD and ΞD+1. More precisely, we have
ẼD+1 = ∑
ΞD+1
( l′0
f + g′0 + g ′ 1
+ a(g′0 + l ′ 2)
(f + g′0 + g ′ 1)f
) Pa,f,D+1(l ′ 0, l ′ 2, g ′ 0, g ′ 1)
= ∑ ΞD {( l0 f + g0 + g1 + 1 + a(g0 + l2 + 1) (f + g0 + g1 + 1)f ) l1 + l2 − g0 D Pa,f,D(l0, l2, g0, g1)
+ ( l0 f + g0 + g1 + 1 + a(g0 + l2) (f + g0 + g1 + 1)f )f − a− l1 − g1 D Pa,f,D(l0, l2, g0, g1)
+ ( l0 f + g0 + g1 + 1 + a(g0 + l2 + 1) (f + g0 + g1 + 1)f ) l1 D Pa,f,D(l0, l2, g0, g1)
+ ( l0 − 1 f + g0 + g1 + 1 + a(g0 + l2 + 2) (f + g0 + g1 + 1)f ) l0 D Pa,f,D(l0, l2, g0, g1)
+ ( l0 f + g0 + g1 + a(g0 + l2) (f + g0 + g1)f )D − f + g0 + g1 D Pa,f,D(l0, l2, g0, g1) } .
The increment can be computed as
δ̃D , ẼD+1 − ẼD = ∑ ΞD { f − g0 − g1 D [( l0 f + g0 + g1 + 1 − l0 f + g0 + g1 ) + ( a(g0 + l2 + 1) f + g0 + g1 + 1 − a(g0 + l2) f + g0 + g1 )] − l0 D(f + g0 + g1 + 1) − a(f − a− l1 − g1)− al0 Df(f + g0 + g1 + 1) } Pa,f,D(l0, l2, g0, g1)
= ∑ ΞD { (f − g0 − g1)[a(f + g1 − l2)− fl0] Df(f + g0 + g1)(f + g0 + g1 + 1) − (f − a)l0 + a(f − a− l1 − g1) Df(f + g0 + g1 + 1) } Pa,f,D(l0, l2, g0, g1)
= ∑ ΞD 2af(l1 + g1)− 2f(f − a)l0 − 2a(f − a)(g0 + g1) Df(f + g0 + g1)(f + g0 + g1 + 1) Pa,f,D(l0, l2, g0, g1)
= E [2af(l1 + g1)− 2f(f − a)l0 − 2a(f − a)(g0 + g1)
Df(f + g0 + g1)(f + g0 + g1 + 1) ] = E
[2af(f − a− h1)− 2f(f − a)l0 − 2a(f − a)(g0 + g1 + f − f) Df(f + g0 + g1)(f + g0 + g1 + 1) ] = E
[ 4a(f − a) D(f + g0 + g1)(f + g0 + g1 + 1) ] − E [ 2ah1 + 2(f − a)l0 D(f + g0 + g1)(f + g0 + g1 + 1) ] − E [ 2a(f − a) Df(f + g0 + g1 + 1) ] , 4a(f − a)E0 − 2aE1 − 2(f − a)E2 − 2a(f − a)E3, (26)
where E0 = E [ 1 D(f + g0 + g1)(f + g0 + g1 + 1) ] , E1 = E [ h1 D(f + g0 + g1)(f + g0 + g1 + 1) ] ,
E2 = E [ l0 D(f + g0 + g1)(f + g0 + g1 + 1) ] , E3 = E [ g2 Df(f + g0 + g1 + 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,f,D(l0, l2, g0, g1)
= D−f−1∑ s=max(0,D−2f+a) (D − f − s)(D − f)!(f − a− 1)! [D − (f + g0 + g1)]![(f + g0 + g1)−D + s]!g1!(D − f − s− g1)!
(a− 1)! (g0 + g1 − l2)![D − s+ l2 − (f + g0 + g1)]!(f − a− l1 − g1)!(f + g1 + l1 −D + s)!l0!(a− l0 − 1)! a!(f − a)!(D − f − 1)!
(D − 1)! .
Denote a′ = a− 1, f ′ = f − 1, D′ = D − 1 and l′0 = l0 − 1. We have
E2 = ∑ ΞD l0 D(f + g0 + g1)(f + g0 + g1 + 1) Pa,f,D(l0, l2, g0, g1)
= ∑ ΞD a(a− 1) D − 1 · 1 D(f + g0 + g1)(f + g0 + g1 + 1)
D′−f ′−1∑ s=max(0,D′−2f ′+a′) (D′ − f ′ − s)(D′ − f ′)!(f ′ − a′ − 1)! [D′ − (f ′ + g0 + g1)]![(f ′ + g0 + g1)−D′ + s]!g1!(D′ − f ′ − s− g1)!
(a′ − 1)! (g0 + g1 − l2)![D′ − s+ l2 − (f ′ + g0 + g1)]!(f ′ − a′ − l1 − g1)!(f ′ + g1 + l1 −D′ + s)!l′0!(a′ − l′0 − 1)! a′!(f ′ − a′)!(D′ − f ′ − 1)!
(D′ − 1)! = ∑
ΞD−1
a(a− 1) D − 1
1
D(f + g0 + g1)(f + g0 + g1 + 1) Pa−1,f−1,D−1(l0, l2, g0, g1)
= a(a− 1) D − 1 Ea−1,f−1,D−1 [ 1 D(f + g0 + g1)(f + g0 + g1 + 1) ] , a(a− 1) D − 1 Ē.
Here the subscript means that we are taking expectation w.r.t the set sizes when the number of “O”, “×” and “−” points is (a− 1, f − 1, D − 1). By symmetry, it can be shown similarly that
E1 = (f − a)(f − a− 1)
D − 1 Ea,f−1,D−1 [ 1 D(f + g0 + g1)(f + g0 + g1 + 1) ] = (f − a)(f − a− 1) D − 1 Ē.
Substituting above results into (26), we obtain
δ̃D = 2a(f − a)[2E0 − f − 2 D − 1 Ē − E3].
To computeE0, note that with a, f andD, variable g2 is distributed as hyper(D−1, D−f,D−f−1). For Ē, the distribution becomes hyper(D− 2, D− f,D− f − 1). Since f + g0 + g1 = D− g2, we deduce
E0 = D−f−1∑ s=max(0,D−2f)
1
D(D − s)(D − s+ 1)
( D−f−1
s
)( f D−f−s )(
D−1 D−f ) =
D−f−1∑ s=max(0,D−2f)
1 D(D − s)(D − s+ 1) (D − f − 1)!f ! s!(D − f − s− 1)!(D − f − s)!(−D + 2f + s)! (D − f)!(f − 1)! (D − 1)! ,
and
Ē = D−f−1∑ s=max(0,D−2f+1)
1
D(D − s)(D − s+ 1)
( D−f−1
s
)( f−1 D−f−s )(
D−2 D−f ) =
D−f−1∑ s=max(0,D−2f+1)
1 D(D − s)(D − s+ 1) (D − f)!(f − 2)! (D − 2)! ·
(D − f − 1)!(f − 1)! s!(D − f − s− 1)!(D − f − s)!(−D + 2f + s− 1)! .
For ∀D ≥ f , we have
f − 2 D − 1
Ē ≤ D−f−1∑
s=max(0,D−2f)
(f − 2)(D − 1)(−D + 2f + s) D(D − 1)f(f − 1)(D − s)(D − s+ 1)
(D − f − 1)!f ! s!(D − f − s− 1)!(D − f − s)!(−D + 2f + s)! (D − f)!(f − 1)! (D − 1)!
≤ E [ (f − 2)(f − (D − f − g2)) Df(f − 1)(D − g2)(D − g2 + 1) ] < E
[ (f − g0 − g1) Df(f + g0 + g1)(f + g0 + g1 + 1) ] .
Consequently, we have δ̃D > 2a(f − a)E [ 2 D(f + g0 + g1)(f + g0 + g1 + 1) − f − g0 − g1 Df(f + g0 + g1)(f + g0 + g1 + 1)
− f + g0 + g1 Df(f + g0 + g1)(f + g0 + g1 + 1) ] = 0,
and note that this holds for ∀D ≥ K. The proof is complete.
A.6 PROOF OF THEOREM 3.5
Theorem 3.5 (Uniform Superiority). For any two binary vectors v,w ∈ {0, 1}D with J 6= 0 or 1, it holds that V ar[Ĵσ,π(v,w)] < V ar[ĴMH(v,w)].
Proof. By assumption we have 0 < a < f . To compare V ar[Ĵσ,π] with V ar[ĴMH ] = J(1−J) K = J K + (K−1)J2 K −J
2, it suffices to compare Ẽ with J2. WhenD = f , we know that the location vector x of (v,w) contains no “−” elements. It is easy to verify that in this case, |G0| = |G1| = |L2| = 0, and |L0| follows hyper(f − 1, a, a− 1). By Theorem 3.2, it follows that when D = f ,
ẼD = 1
f E[|L0|] = a(a− 1) f(f − 1) = JJ̃ < J2.
Recall the definition J̃ = a−1f−1 , which is always less than J . On the other hand, as D →∞, we have |L0| → 0, |L2| → a, |G0| → a and |G1| → f − a. We can easily show that
ẼD → J2, as D →∞.
By Lemma 3.4, the sequence (Ẽf , Ẽf+1, Ẽf+2, ...) is strictly increasing. Since it is convergent with limit J2, by the Monotone Convergence Theorem we know that ẼD < J2, ∀D ≥ f .
A.7 PROOF OF PROPOSITION 3.6
Proposition 3.6 (Consistent Improvement). Suppose f is fixed. In terms of a, the variance ratio ρ(a) = V ar[ĴMH(v,w)]
V ar[Ĵσ,π(v,w)] is constant for any 0 < a < f .
Proof. Let Ẽ be defined as in Theorem 3.2. Assume that D and f are fixed and a is variable. Firstly, we can write the variance ratio explicitly as
ρ(a) = J−J2 K
J K + (K+1)Ẽ K − J2
= 1− J
1− J − (K − 1)(J − ẼJ ) .
We now show that the term J − ẼJ = C(1 − J), where C is some constant independent of J (i.e., a). Then, for fixed D and f , by cancellation ρ(a) would be constant for all 0 < a < f . We have
J − Ẽ J = a f − Ea,f,D [ fl0 a(f + g0 + g1) + g0 + l2 f + g0 + g1 ] = E
[a2(f + g0 + g1)− f2l0 − af(g0 + l2) af(f + g0 + g1) ] = E
[a(a− f)(g0 + g1) + a2f + afg1 − f2l0 − afl2 af(f + g0 + g1) ] = E
[a(a− f)(g0 + g1) + af(l0 + l1) + afg1 − f2l0 af(f + g0 + g1) ] = E
[a(a− f)(g0 + g1) + f(a− f)l0 + af(f − a− h1) af(f + g0 + g1) ] , (27)
where we use the constraints (10) that l0 + l1 + l2 = a and l1 + g1 +h1 = f − a. We now study the three terms respectively. We have
E [a(a− f)(g0 + g1) af(f + g0 + g1) ] = −(1− J)E [ g0 + g1 f + g0 + g1 ] , −E′(1− J).
We have shown in the proof of Lemma 3.4 that
Ea,f,D [ l0 f + g0 + g1 ] = a(a− 1) D − 1 Ea−1,f−1,D−1 [ 1 f + g0 + g1 ] , a(a− 1) D − 1 E∗,
and by symmetry it holds that
Ea,f,D [ h1 f + g0 + g1 ] = (f − a)(f − a− 1) D − 1 E∗.
Note that Since f is fixed, (|G0| + |G1|) is distributed independent of a. Consequently, E′ and E∗ are both independent of a. Next, we obtain
E [ f(a− f)l0 af(f + g0 + g1) ] = −(1− J)f(a− 1) D − 1 E∗,
and
E [ af(f − a− h1) af(f + g0 + g1) ] = (1− J)fE∗ − (1− J)f(f − a− 1) D − 1 E∗.
Summing up the terms and substituting into (27), we derive
J − Ẽ J = C(1− J),
where C = −E′ + (f − f(f−2)D−1 )E ∗, which is independent of a. Taking into ρ(a), we get
ρ(a) = 1− J
1− J − (K − 1)C(1− J) =
1
1− (K − 1)C ,
which is a constant only depending on f , D and K. This completes the proof.
A.8 PROOF OF THEOREM 5.1
Proof. Denote E[1k] := E[1{hk(v) = hk(w)}] for any 1 ≤ k ≤ K. We first recall some notations. We have v,w ∈ {0, 1}D, and a and f are defined in (5). Denote B1 = {i : xi = O}, B2 = {i : xi = ×} and B3 = {i : xi = −} as the sets of three types of points, respectively. For a ≤ j ≤ D and 1 ≤ k ≤ K, define
A−(j) = {xi : (i+ k − 1 mod D) + 1 ≤ j}, A+(j) = {xi : (i+ k − 1 mod D) + 1 > j}.
Let n−,1(j) = |{xi = O : i ∈ A−(j)}| be the number of “O” points in A−(j). Analogously let n−,2(j), n−,3(j) be the number of “×” and “−” points in A−(j), and n+,1(j), n+,2(j), n+,3(j) be the number of “O”, “×” and “−” points in A+(j). For any i, denote i∗ = (i+ k − 1 mod D) + 1, i# = (i− k − 1 mod D) + 1. Our analysis starts with the decomposition of hash collision probability,
E[1k] = P [ hk(v) = hk(w) ] = D∑ j=1 P [ hk(v) = hk(w) = j ] , (28)
where recall h(·) is the hash sample. Consider the process for generating the hash. As before, we look at the location vector x. In Method 2, we first permute x by π to get π(x). Then the k-th hash samples collide if the minimum of π→k(π(x)) is “O”. One key observation is that, when applying π→k, the random index for the i-th element in π(x) is exactly the one used for xi# (shifted backwards) in the initial permutation. A toy example in provided in Figure 8 to help understand the reasoning.
Further denote setM = {π(i) : π(i) /∈ B3} be the collection of indices of initially permuted vector π(x) that are not “−” points, andM←k = (M− k − 1 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 π→k(π(x)), the 8-th element (“O”) in π(x) will be permuted to the same index of the 8 − 2 = 6-th element in x, which equals to 4. It is important to notice that, when considering the k-th collision, only points inM←k matters. Hence, we deduct:
• (Collision condition) Denote i = arg mint∈M←k π(xt) be the location of minimal permutation index inM←k. The k-th collision occurs at j i.f.f. π(i) = j, and the i∗-th element in π(x) must be a “O” point. Recall the definition i∗ = (i+ k − 1 mod D) + 1.
In Figure 8, consider i = 6 and j = 4 for example. Above condition means that the i = 6-th element in x (“−” 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 i + k = 6 + 2 = 8-th element in π(x) must be a “O”. Figure 8 exactly satisfies the condition, so it depicts a collision. Mathematically, we have
E[1k] = D∑ j=1 P [ hk(v) = hk(w) = j ]
= D∑ j=1 D∑ i=1 P [ π(i) = j, π−1(i∗) ∈ B1 ] , (29)
where i = arg mint∈M←k π(xt). In this expression, everything is random of π, except for the set B1 which is fixed given the data. Now we will focus on deriving the probability for a fixed i and j in (29). Our analysis will be conditional on the collection of variables Z which is defined as follows. Let z−,1, z−,2 and z−,3 be the number of “O”, “×” and “−” points in A−(j) ∩Mc←k, and z+,1, z+,2 and z+,3 be the number of “O”, “×” and “−” points inA+(j)∩Mc←k, respectively. HereMc←k represents the complement ofM←k. Notice that Z (and its density function) depends on different j since A−(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 = (z−,k|31, z+,k|31) follows hyper(D,D− f, n−,k(j)|31, n+,k(j)|31). Denote the domain of Z and Θj . Conditional on Z, we obtain
E[1k] = D∑ j=1 ∑ Z∈Θj D∑ i=1 P [ π(i) = j, π−1(i∗) ∈ B1|Z ] Pj [ Z ]
= D∑ j=1 ∑ Z∈Θj D∑ i=1 P [ π−1(i∗) ∈ B1|π(i) = j, Z ] P [ π(i) = j|Z ] Pj [ Z ] , D∑ j=1 ∑ Z∈Θj D∑ i=1 Γ(i, j)Pj [ Z ] , (30)
with i = arg mint∈M←k π(xt). We will carefully compute the probabilities in the summation. Basically, the key is that elements inM need to be controlled, i.e. smaller than j, and other positions can be arbitrary. Given Z, this means that we need to put r1 = a − z−,1 − z+,1 type “O” points, r2 = f −a−z−,2−z+,2 type “×” points and r3 = D−f −z−,3−z+,3 type “−” points no smaller than j, with π(i) = j exactly. Also note that there are fixed b0 = ∑3 k=1 z+,k type “−” points no smaller than j.
With all these definitions and reasoning, we are ready to proceed with the proof. Based on xi, we have three general cases.
1) xi ∈ B1. The first case is that xi = O. Case 1a) j < i∗. Firstly, we consider the case where j < i∗. By combinatorial theory we have
P [ π(i) = j|Z ] = P [ π(i) = j|π−1(j) /∈ B3, Z ] P [ π−1(j) /∈ B3|Z ] = 1
r1 + r2
( b0 r3 )( D−j−b0 r1+r2−1 )( D−f r3 )( f r1+r2 )P[π−1(j) /∈ B3|Z] , P̃1 · P [ π−1(j) /∈ B3|Z ] , (31)
where the second probability is that the j-th element in π(x) is not “−”. Conditional on Z, the probability is dependent on j#:
P [ π−1(j) /∈ B3|Z ] = 3∑ p=1 1{j# ∈ Bp}(1− z−,p n−,p(j) ).
Combining with (31) we obtain
P [ π(i) = j|Z ] = P̃1 3∑ p=1 1{j# ∈ Bp}(1− z−,p n−,p(j) ). (32)
Next we compute P [π−1(i∗) ∈ B1|π(i) = j, Z]. Note that given the conditions, π−1(i∗) has two cases: 1) it comes fromM←k (i.e. it is one of the elements with red bold border); 2) Otherwise. We then can write
P [ π−1(i∗) ∈ B1|π(i) = j, Z ] = P [ π−1(i∗) ∈ B1|π−1(i∗) ∈M←k, π(i) = j, Z ] P [ π−1(i∗) ∈M←k|π(i) = j, Z
] + P [ π−1(i∗) ∈ B1|π−1(i∗) /∈M←k, π(i) = j, Z ] P [ π−1(i∗) /∈M←k|π(i) = j, Z
] = (1− z+,1
n+,1(j) ) [ r1 + r2 − 1 D − j − b0 r1 − 1 r1 + r2 − 1 + (1− r1 + r2 − 1 D − j − b0 ) a− r1 f − r1− r2 ] , (1− z+,1
n+,1(j) )
[ r1 − 1
D − j − b0 + (1− r1 + r2 − 1 D − j − b0 )J∗ ]
, (1− z+,1 n+,1(j) )J̄1. (33)
Combining (32) and (33), we obtain when i ∈ B1 and j < i∗,
Γ(i, j) = 3∑ p=1 1{j# ∈ Bp}(1− z−,p n−,p(j) )(1− z+,1 n+,1(j) )P̃1J̄1. (34)
Case 1b) j = i∗. Similarly approach also applies to the situation with j = i∗. In this case, P [ π−1(j) /∈ B3|Z ] = (1− z−,1
n−,1(j) )P̃1, P [π
−1(i∗) ∈ B1|π(i) = j, Z] = 1. (35)
The equations are because (i∗)# = i ∈ B1, and equivalently, π−1(i∗) = π−1(j) = i ∈ B1. Case 1c) j > i∗. I this case, we still have
P [ π(i) = j|Z ] = P̃1 3∑ p=1 1{j# ∈ Bp}(1− z−,p n−,p(j) ),
but the probability of π−1(i∗) being “O” is different. Since j > i∗, this event now depends on z−,p, p = 1, 2, 3. More specifically,
P [π−1(i∗) ∈ B1|π(i) = j, Z]
= [ 1{j# ∈ B1}(1−
z−,1 n−,1(j)− 1 ) + ∑ p=2,3 1{j# ∈ Bp}(1− z−,p n−,p(j) )
] J∗.
Therefore, when i ∈ B1 and j > j∗, it holds that
Γ(i, j) = (1− z−,1 n−,1(j) )
[ 1{j# ∈ B1}(1−
z−,1 n−,1(j)− 1 ) + ∑ p=2,3 1{j# ∈ Bp}(1− z−,p n−,p(j) )
] J∗.
(36)
2) xi ∈ B2. The case where xi ∈ B2 can be analyzed using similar arguments. For conciseness, we mainly present the final results.
Case 2a) j < i∗. The calculation ends up in the same form. We have
P [ π(i) = j|Z ] = P̃2 3∑ p=1 1{j# ∈ Bp}(1− z−,p n−,p(j) ),
with P̃2 = P̃1. In addition, P [ π−1(i∗) ∈ B1|π(i) = j, Z ] = (1− z+,2
n+,2(j) )J̄2,
where J̄2 = r1D−j−b0 + (1− r1+r2−1 D−j−b0 )J ∗. Hence, when xi ∈ B2 and j < i∗, we have
Γ(i, j) = 3∑ p=1 1{j# ∈ Bp}(1− z−,p n−,p(j) )(1− z+,2 n+,2(j) )P̃2J̄2. (37)
Case 2b) j = i∗. In this case, Γ(i, j) simply equals to 0, since π−1(i∗) = π−1(j) ∈ B2. The probability of π−1(i∗) being “O” is 0.
Case 2c) j > i∗. Omitting the details, we have
Γ(i, j) = (1− z−,2 n−,2(j) )
[ 1{j# ∈ B2}(1−
z−,2 n−,2(j)− 1 ) + ∑ p=1,3 1{j# ∈ Bp}(1− z−,p n−,p(j) )
] J∗.
(38)
2) xi ∈ B3. Case 3a) j < i∗. The expression is different from previous two, in that we need π−1(j) ∈ B3.
P [ π(i) = j|Z ] = P [ π(i) = j|π−1(j) ∈ B3, Z ] P [ π−1(j) ∈ B3|Z ] = P̃3
3∑ p=1 1{j# ∈ Bp} z−,p n−,p(j) ,
where
P̃3 = 1
r3
( b0 r3−1 )( D−j−b0 r1+r2 )( D−f r3 )( f r1+r2
) . Moreover, we have
P [ π−1(i∗) ∈ B1|π(i) = j, Z ] = (1− z+,3
n+,3(j) )J̄3,
with J̄3 = r1D−j−b0 + (1− r1+r2 D−j−b0 )J ∗. Combining parts together we obtain
Γ(i, j) = 3∑ p=1 1{j# ∈ Bp} z−,p n−,p(j) (1− z+,3 n+,3(j) )P̃3J̄3. (39)
Case 3b) j = i∗. By same reasoning as Case 2a), Γ(i, j) = 0.
Case 3c) j > i∗. We have in this case
Γ(i, j) = [ 1{j# ∈ B3}
z−,3 n−,3(j) n−,3(j)− z−,3 n−,3(j)− 1 + (1− z−,3 n−,3(j) ) ∑ p=1,2 1{j# ∈ Bp} z−,p n−,p(j)
] J∗
= 3∑ p=1 1{j# ∈ Bp} z−,p n−,p(j) (1− z−,3 − 1{p = 3} n−,3(j) − 1{p = 3})J∗. (40)
Finally, combining (30), (34), (35), (36), (37), (38), (39) and (40) and re-organizing terms, the proof is complete.
B MORE NUMERICAL JUSTIFICATION 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 a total of D = 216 documents. The key statistics of the 120 selected word pairs are presented in Table 1. Those 120 pairs of words are more or less randomly selected except that we make sure they cover a wide spectrum of data distributions. Denote d as the number of non-zero entries in the vector. Table 1 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 to 0.95.
In Figures 9 - 16, we plot the empirical MSE along with the empirical bias2 for Ĵπ,π , as well as the empirical MSE for Ĵσ,π . Note that for D this large, it is numerically difficult to evaluate the theoretical variance formulas. From the results in the Figures, we can observe
• For all the data pairs, the MSE of C-MinHash-(π, π) estimator overlaps with the empirical MSE of C-MinHash-(σ, π) estimator for all K from 1 up to 4096.
• The bias2 is several orders of magnitudes smaller than the MSE, in all data pairs. This verifies that the bias of Ĵπ,π is extremely small in practice and can be safely neglected.
We have many more plots on more data pairs. Nevertheless, we believe the current set of experiments on this “Words” dataset should be sufficient to verify that, the proposed C-MinHash-(π, π) could give indistinguishable Jaccard estimation accuracy in practice compared with C-MinHash-(σ, π).

title: C-MINHASH: IMPROVING MINWISE HASHING