SuperMinHash – A New Minwise Hashing Algorithm
for Jaccard Similarity Estimation
Otmar Ertl
Linz, Austria
otmar.ertl@gmail.com

arXiv:1706.05698v1 [] 18 Jun 2017

ABSTRACT
This paper presents a new algorithm for calculating hash signatures
of sets which can be directly used for Jaccard similarity estimation.
The new approach is an improvement over the MinHash algorithm,
because it has a better runtime behavior and the resulting signatures
allow a more precise estimation of the Jaccard index.

1

P(h j (A) = h j (B)) = P(h j (A ∩ B) = h j (A ∪ B)) =

INTRODUCTION
|A ∩ B|
J=
|A ∪ B|

is a measure for the similarity of two sets A and B. If one is interested
in pairwise similarities of many sets the direct calculation is often
computationally too expensive. Therefore, different algorithms [1, 3,
5, 7–9] have been proposed, which first calculate hash signatures of
individual sets. The Jaccard index can then be quickly determined
given only the signatures of the corresponding two sets. Each
signature contains condensed information about its corresponding
set which is relevant for Jaccard index estimation.

MinHash Algorithm

The MinHash algorithm [1] was the first approach to calculate
signatures suitable for Jaccard index estimation. The signature
consists of m values (h 0 , h 1 , . . . , hm−1 ) which are defined for a
given data set D by
h j (D) := min (r j (d)).
d ∈D

(1)

The functions r j are independent and uniform hash functions with
value range [0, 1). The signature size m is a free parameter and
allows trading space and computation time for more precise estimates.

Input: (d 0 , d 1 , . . . , dn−1 )
Output: (h 0 , h 1 , . . . , hm−1 ) ∈ [0, 1)m
(h 0 , h 1 , . . . , hm−1 ) ← (∞, ∞, . . . , ∞)
for i ← 0, 1, . . . , n − 1 do
initialize pseudo-random generator with seed di
for j ← 0, 1, . . . , m − 1 do
r ← uniform random number from [0, 1)
h j ← min(h j , r )
end for
end for

(3)

is an unbiased estimator for the Jaccard index. I denotes the indicator function. Since all signature values are independent and
identically distributed, the sum of indicators corresponds to a binomial distribution with sample size m and success probability J .
Hence, the variance of the estimator is given by
J (1 − J )
.
(4)
m
Algorithm 1 demonstrates the calculation of the MinHash signature for a given input data sequence d 0 , d 1 , . . . , dn−1 of length
n. Since the input data may contain duplicates we generally have
|D| ≤ n for the cardinality of the set D = {d 0 , d 1 , . . . , dn−1 }.
For simplicity Algorithm 1 and also the algorithms that are presented later are expressed in terms of a pseudo-random number
generator. Assuming independent and uniform hash functions r j
the sequence r 0 (d), r 1 (d), . . . behaves statistically like the output of
an ideal pseudo-random generator with seed d. By chaining the
hash values of different hash functions random bit sequences of
arbitrary length can be realized. In practice, the next hash function
is evaluated, only if all bits of the previous hash value have been
consumed.
The runtime complexity of MinHash is O(mn), because the inner
loop is executed mn times. Since m is large for many applications,
more efficient algorithms are desirable.
Var( Jˆ) =

1.2
Algorithm 1 MinHash algorithm.

|A ∩ B|
= J . (2)
|A ∪ B|

Here we used the equivalence h j (A) = h j (B) ⇔ h j (A ∩ B) =
h j (A ∪ B). Therefore,
m−1
1 Õ
I (h j (A) = h j (B))
Jˆ =
m j=0

The Jaccard index

1.1

The probability that signature values are equal for two different
sets A and B corresponds to the Jaccard index

One Permutation Hashing

The first approach that significantly reduced the calculation time
was one permutation hashing [5]. The idea is to divide the input
set D randomly into m disjoint subsets D 0 , D 1 , . . . , Dm−1 . The hash
signature is calculated using a single hash function r
h j (D) := min (r (d)).
d ∈D j

This procedure results in an optimal runtime complexity of O(m+n).
Unfortunately, for small input sets, especially if |D| < m, many subsets are empty and corresponding signature values are undefined.
Various densification algorithms have been proposed to resolve this
problem [7–9], which fill undefined positions in the signature by
copying defined values in such a way that estimator (3) remains

unbiased. However, all densified hash signatures lead to less precise
Jaccard index estimates compared to MinHash for small data sets
with |D|  m. In addition, the best densification scheme in terms
of precision presented in [7] has a runtime that scales quadratically
with signature size m for very small data sets [3]. Another disadvantage is that signatures of different sets cannot be longer merged
after densification to construct the signature for the corresponding
union set.

1.3

Here we extended (1) by adding elements of a random permutation


0
1
···
m−1
π (d) =
π0 (d) π1 (d) · · · πm−1 (d)
that is generated for each input element d.
Since the values r j (d 0 ) + π j (d 0 ), . . . , r j (dn−1 ) + π j (dn−1 ), are still
mutually independent and uniformly distributed over [0, m), (2) also
holds here and the Jaccard index estimator (3) will give unbiased
results. However, in contrast to MinHash, the signature values
h 0 , h 1 , . . . , hm−1 are no longer independent. As we will see, this is
the reason for the improved precision when estimating the Jaccard
index for small sets.
The new approach requires the generation of random permutations for each input data element. Fisher–Yates shuffling is the
standard algorithm for this purpose [4]. The shuffling algorithm
uses uniformly distributed integer numbers. An algorithm for the
generation of strict uniform random integers that is efficient regarding random bit consumption is described in [6].
A straightforward implementation of (5) would look like Algorithm 2. Obviously, the runtime complexity is still O(nm). However,
in the following we describe a couple of algorithmic optimizations
which finally end up in the new SuperMinHash algorithm.

Fast Similarity Sketching

Recently, a new algorithm called fast similarity sketching has been
presented [3] that achieves a runtime complexity of O(n + m log m)
for the case that the input does not contain duplicates (n = |D|). It
was also shown that the variance of the Jaccard index estimator
is significantly improved for small data sets. However, in contrast
to MinHash it cannot be directly used as streaming algorithm,
because multiple passes over the input data are needed. Moreover,
the computation time is approximately twice that of MinHash for
small data sets with |D|  m.

1.4

Outline

In the following we present a new algorithm for the calculation of
signatures appropriate for Jaccard index estimation. We call the new
algorithm SuperMinHash, because it generally supersedes MinHash.
We will prove that the variance of the Jaccard index estimator (3) is
strictly smaller for same signature sizes. In addition, we will show
that the runtime for calculating the signatures is comparable for
small data sets while it is significantly better for larger data sets as
it follows an O(n + m log2 m) scaling law for n = |D|. Furthermore,
like MinHash, the new algorithm requires only a single pass over
the input data, which allows a straightforward application to data
streams or big data sets that do not fit into memory as a whole.

2

2.1

Algorithm 3 Transformed version of Algorithm 2.

SUPERMINHASH ALGORITHM

Input: (d 0 , d 1 , . . . , dn−1 )
Output: (h 0 , h 1 , . . . , hm−1 ) ∈ [0, m)m
(h 0 , h 1 , . . . , hm−1 ) ← (∞, ∞, . . . , ∞)
allocate array (p0 , p1 , . . . , pm−1 )
(q 0 , q 1 , . . . , qm−1 ) ← (−1, −1, . . . , −1)
for i ← 0, 1, . . . , n − 1 do
initialize pseudo-random generator with seed di
for j ← 0, 1, . . . , m − 1 do
r ← uniform random number from [0, 1)
k ← uniform random number from {j, . . . , m − 1}
if q j , i then
qj ← i
pj ← j
end if
if qk , i then
qk ← i
pk ← k
end if
swap p j and pk
hp j ← min(hp j , r + j)
end for
end for

The new algorithm is based on a hash signature defined by
h j (D) := min (r j (d) + π j (d)).
d ∈D

Optimization

As first step towards our final algorithm we merge both inner
loops in Algorithm 2 and eliminate the initialization of array
(p0 , p1 , . . . , pm−1 ) as demonstrated by Algorithm 3. The trick is
to introduce a second array (q 0 , q 1 , . . . , qm−1 ) which is used to
mark corresponding entries in (p0 , p1 , . . . , pm−1 ) as initialized during the j-th inner loop cycle. pk is regarded as initialized if and only
if qk = j. Otherwise, pk is set equal to k when accessed first and
qk is simultaneously set equal to j to flag the entry as initialized.

(5)

Algorithm 2 Straightforward calculation of the new signature
defined by (5) using Fisher–Yates shuffling.
Input: (d 0 , d 1 , . . . , dn−1 )
Output: (h 0 , h 1 , . . . , hm−1 ) ∈ [0, m)m
(h 0 , h 1 , . . . , hm−1 ) ← (∞, ∞, . . . , ∞)
for i ← 0, 1, . . . , n − 1 do
initialize pseudo-random generator with seed di
(p0 , p1 , . . . , pm−1 ) ← (0, 1, . . . , m − 1)
for j ← 0, 1, . . . , m − 1 do
k ← uniform random number from {j, . . . , m − 1}
swap p j and pk
end for
for j ← 0, 1, . . . , m − 1 do
r ← uniform random number from [0, 1)
h j ← min(h j , r + p j )
end for
end for
2

A second modification compared to Algorithm 2 is that the signature value update h j ← min(h j , r + p j ) has been replaced by
hp j ← min(hp j , r + j). Both variants are statistically equivalent,
because it does not make any difference, whether we interpret the
randomly generated permutation as π (d) or as its inverse π −1 (d).
Algorithm 3 shows potential for further improvement. We see
that the signature value updates r + j are strictly increasing within
the inner loop. Therefore, if we knew the current maximum of all
current signature values, we would be able to leave the inner loop
early. The solution is to maintain a histogram over the integral
parts of the current signature values
(Í
m−1 I (bh c = k)
k ∈ {0, 1, . . . , m − 2}
j
j=0
bk := Ím−1
j=0 I (h j ≥ m − 1) k = m − 1
and also to keep track of the maximum non-zero histogram entry
a := max({j | b j > 0}).
Figure 1: The function α(m, u) over u for different signature
sizes m. The crosses represent values obtained through simulations.

Algorithm 4 SuperMinHash algorithm which is an optimized version of Algorithm 3.
Input: (d 0 , d 1 , . . . , dn−1 )
Output: (h 0 , h 1 , . . . , hm−1 ) ∈ [0, m)m
(h 0 , h 1 , . . . , hm−1 ) ← (∞, ∞, . . . , ∞)
allocate array (p0 , p1 , . . . , pm−1 )
(q 0 , q 1 , . . . , qm−1 ) ← (−1, −1, . . . , −1)
(b0 , b1 , . . . , bm−2 , bm−1 ) ← (0, 0, . . . , 0, m)
a ←m−1
for i ← 0, 1, . . . , n − 1 do
initialize pseudo-random generator with seed di
j←0
while j ≤ a do
r ← uniform random number from [0, 1)
k ← uniform random number from {j, . . . , m − 1}
if q j , i then
qj ← i
pj ← j
end if
if qk , i then
qk ← i
pk ← k
end if
swap p j and pk
if r + j < hp j then
j 0 ← min(bhp j c, m − 1)
hp j ← r + j
if j < j 0 then
bj0 ← bj0 − 1
bj ← bj + 1
while ba = 0 do
a ←a−1
end while
end if
end if
j ←j+1
end while
end for

Knowing a allows escaping the inner loop as soon as j > a, because
further signature value updates are not possible in this case. The
result of all these optimizations is the new SuperMinHash algorithm
as shown in Algorithm 4.

2.2

Precision

As proven in the appendix the variance of estimator (3) for the new
signature is
J (1 − J )
Var( Jˆ) =
α(m, u)
(6)
m
where u := |A ∪ B| is the union cardinality. The function α(m, u) is
defined as
Ím−1 u
l ((l + 1)u + (l − 1)u − 2l u )
α(m, u) := 1 − l =1
.
(7)
(m − 1)u−1mu (u − 1)
The function is always in the range [0, 1), because the term (l +
1)u + (l − 1)u − 2l u is positive for u > 1. α(m, u) corresponds to
the reduction factor of the variance relative to that of MinHash
signatures (4). Fig. 1 shows the function for different values of m.
Interestingly, α(m, u) only depends on the union cardinality u and
the signature size m and does not depend on the Jaccard index J .
Compared to MinHash the variance is approximately by a factor of
two smaller in case u < m.
To verify (6) we have conducted some simulations to determine
the variance of the Jaccard index estimator for two random sets A
and B experimentally. We considered the cases |A \ B| = |B \ A| =
|A ∩ B| = 2k with u = 3 · 2k and the cases |A \ B|/2 = |B \ A| =
|A ∩ B| = 2k with u = 4 · 2k both for k ∈ {0, 1, . . . , 11}. For each
case 100 000 different triples of disjoint sets S A\B , S B\A , and S B∩A
have been randomly generated with cardinalities |A \ B|, |B \ A|,
and |A ∩ B|, respectively. Then the sets A and B are constructed
using A = S A\B ∪ S A∩B and B = S B\A ∪ S A∩B . After calculating the
corresponding hash signatures, their common Jaccard index has
been estimated. The estimates of all 100 000 simulation runs have
3

been used to calculate the variance and also α(m, u) by dividing by
the theoretical MinHash variance (4). The experimental results are
shown as crosses in Fig. 1 and confirm the theoretically derived
formula (7).
For all simulation runs we used the 128-bit version of the MurmurHash3 algorithm which also allows to specify a seed. We used a
predefined sequence of seed values to generate an arbitrary number
of hash values for a given data element, which are used as bit source
for pseudo-random number generation.

2.3

Runtime

To analyze the runtime of Algorithm 4 we first consider the case
that all inserted elements are distinct (n = |D|). The expected
runtime is given by the expected total number of inner (while) loop
iterations denoted by T = T (n, m) that are needed when inserting
n elements. If ts denotes the average number of element insertions
until a becomes smaller than s, we can write
T (n, m) = n +

m−1
Õ

min(ts , n).

Figure 2: The average number of inner loop iterations in Algorithm 4 per inserted data element over the set size n for
different signature sizes m.

s=1

Since a is smaller than s as soon as each signature value is less
than s, ts can be regarded as the average number of random permutations that are necessary until any value of {0, 1, . . . , s − 1} was
mapped to each signature index. This corresponds to the coupon
collector’s problem with collection size m and group drawings of
size s, where each drawing gives s distinct coupons [10]. In our
case the complete collection corresponds to the m signature indices.
Drawing a group of coupons corresponds to selecting the first s
indices after permuting a list with all m of them.
For the classical coupon collector’s problem with group size s = 1
we have the well known solution [2]

To better understand the runtime of Algorithm 4 compared to
the MinHash algorithm, we investigated the average number of
inner loop cycles per inserted data element T (n, m)/n. For the new
algorithm we expect that that this number starts at m and decreases
to 1 as n → ∞ because of (8). In contrast, the MinHash algorithm
always needs m inner loop iterations regardless of the input data
size n.
Fig. 2 shows the experimentally determined average number of
inner loop cycles for set sizes n = 2k with k ∈ {0, 1, . . . , 20} and
n = 3 · 2k with k ∈ {0, 1, . . . , 19} based on 1000 randomly generated
data sets, respectively. The results indeed show that the amortized
costs for a single data element insertion correspond to a single
inner loop execution as n → ∞. Thus, the runtime performance is
improved up to a factor of m relative to MinHash.
If the input data d 0 , d 1 , . . . , dn−1 contains duplicates, hence
|D| < n, the runtime will be longer, because repeated insertions
of identical values will not change any state in Algorithm 4. If
we assume that the order of input elements is entirely random,
n
the average number of inner loop iterations will be T (|D|, m) |D
|
which gives T (|D|, m)/|D| per inserted element. In the worst case,
if many input elements are equal and sorted, the number of inner
loop iterations per input element is still limited by m and thus equal
to that of MinHash.

t 1 = mHm .
1
1

1
2

1 denotes the m-th harmonic numHere Hm := + + . . . + m
ber. Unfortunately, there is no simple expression for s ≥ 2 [10].
However, it is easy to find an upper bound for ts . Let ρl be the
probability that l drawings are necessary to complete the coupon
collection for the classical case with group size 1. By definition,
Í
Í
we have l∞=1 ρl l = t 1 = mHm with l∞=1 ρl = 1. If l drawings are
necessary to complete the collection for the case s = 1, it is obvious
that not more than dl/se drawings will be necessary for the general
case with group size s. Therefore, we can find the upper bound
  Õ
∞
∞
Õ
l
l + s − 1 mHm + s − 1
ts ≤
ρl
≤
ρl
=
.
s
s
s
l =1

l =1

Using this inequality together with min(ts , n) ≤ ts we get
T (n, m) ≤ n +

m−1
Õ

ts ≤ n + (mHm − 1)Hm−1 + m − 1

3

s=1

= n + O(m log2 m) = O(n + m log2 m).

CONCLUSION

We have presented the SuperMinHash algorithm which can be used
as full replacement for the MinHash algorithm as it has similar or
even better properties as the MinHash algorithm. The new algorithm has comparable runtime for small input sizes, is significantly
faster for larger data sizes, can also be used as streaming algorithm
as it requires only a single pass over the data, and significantly
improves the precision of Jaccard index estimates for small sets.

(8)

Here we used the relationship Hm = O(log m). In any case the
worst case runtime is limited by the maximum number of inner
loop iterations, which is equal to nm, if the shortcut introduced in
Algorithm 4 never comes into play. Thus, the new algorithm never
needs more inner loop cycles than the MinHash algorithm.
4

APPENDIX

1
=
m −z

In order to derive formula (6) for the variance of estimator (3)
when applied to the new signature we first consider the conditional
probability P(h j (A) = h j (B) | hk (A) = hk (B)). For the trivial case
j = k this probability is equal to 1. Therefore, we consider the case
j , k in the following.
If we introduce
d 0 := arg min hk (d)
(9)

=

and use the equivalences h j (A) = h j (B) ⇔ h j (A∩B) = h j (A∪B) ⇔
h j (A ∩ B) < h j (A 4 B) and hk (A) = hk (B) ⇔ d 0 ∈ A ∩ B, where
A 4 B denotes the symmetric difference of sets A and B, we can
write

x ∈ [0, bzc)

(m−1)(m−z)


)(m−1−z)

 (m−x
 (m−1)(m−z)

x ∈ [bzc + 1, m).

x ∈ [bzc, bzc + 1)

= P(h j (d) > x | d , d 0 ∧ hk (d 0 ) = z)

0

(13)

 |A4B |

= (W (x, z))u(1−J ) .

(14)

Here we have used the fact that the complementary cumulative
distribution function of the minimum of independent random variables is identical to the product of the individual complementary
cumulative distribution functions.
Analogously, h j (A∩ B) conditioned on d 0 ∈ A∩ B and hk (d 0 ) = z
is distributed like the minimum of |A ∩ B| − 1 = u J − 1 identically
distributed random variables following (13) and h j (d 0 ) which is
described by (12)

(10)

0

with functions R(z) and S(z) defined as
R(z) := P(hk (d 0 ) < z | d 0 ∈ A ∩ B) = P(hk (d 0 ) < z)
and
S(z) := P(h j (A ∩ B) < h j (A 4 B) | d 0 ∈ A ∩ B ∧ hk (d 0 ) = z),
respectively.
Since hk (d 0 ) is the minimum of u := |A ∪ B| independent uniformly distributed values from [0, m), its cumulative distribution
function is

z u
R(z) = 1 − 1 −
m
and its first derivative is
u
R 0 (z) = u (m − z)u−1 .
(11)
m
To get S(z) we first consider the distribution of h j (d) for any
input element d conditioned on hk (d) = z. The distribution of
h j (d) is uniform over [0, bzc) ∪ [bzc + 1, m), because the integral
part must be different from bzc due to the permutation in (5). The
corresponding complementary cumulative distribution function is

P(h j (A ∩ B) > x | d 0 ∈ A ∩ B ∧ hk (d 0 ) = z)
= P(h j (d 0 ) > x | hk (d 0 ) = z)·
· P(h j (d) > x | d , d 0 ∧ hk (d 0 ) = z)

 |(A∩B)\{d 0 } |

= V (x, z) (W (x, z))u J −1 .

(15)

Using (14) and (15) we can derive S(z)
S(z) = P(h j (A ∩ B) < h j (A 4 B) | d 0 ∈ A ∩ B ∧ hk (d 0 ) = z)
= 1 − P(h j (A ∩ B) > h j (A 4 B) | d 0 ∈ A ∩ B ∧ hk (d 0 ) = z)
∫m P(h j (A ∩ B) > x | d 0 ∈ A ∩ B ∧ hk (d 0 ) = z)·
©
ª
= 1 + ­ ∂P(h j (A 4 B) > x | d 0 ∈ A ∩ B ∧ hk (d 0 ) = z) ® dx
·
¬
0 «
∂x
∫m
∂W (x, z)
dx
= 1 + u(1 − J ) V (x, z) (W (x, z))u−2
∂x

V (x, z) := P(h j (d) > x | hk (d) = z)
x ∈ [0, bzc)
x ∈ [bzc, bzc + 1)
x ∈ [bzc + 1, m).

z


m−1−x


m−1

 (m−1−

bz c)(m−(x − bz c)−z)

P(h j (A 4 B) > x | d 0 ∈ A ∩ B ∧ hk (d 0 ) = z)

P(h j (A) = h j (B) | hk (A) = hk (B))



m − 1 − x


1
=
· m − 1 − bzc
m−1 

m − x


V (x, z 0 )dz 0

Now we are able to determine the complementary cumulative
distribution functions for h j (A 4 B), which is the minimum of
|A 4 B| = u(1 − J ) identically distributed random variables obeying
(13), conditioned on d 0 ∈ A ∩ B and hk (d 0 ) = z

d ∈A∪B

= P(h j (A ∩ B) < h j (A 4 B) | d ∈ A ∩ B)
∫m
=
R 0 (z)S(z)dz

∫m

(12)

0

Next we consider the distribution of h j (d), if d , d 0 and hk (d 0 ) = z.
Due to (9) d , d 0 is equivalent to hk (d) > hk (d 0 ). Furthermore,
hk (d) is uniformly distributed over [z, m). Therefore, we get for the
complementary cumulative distribution function

=1+

u(1 − J )
u−1

∫m
V (x, z)


∂ 
(W (x, z))u−1 dx
∂x

0

∫m
u(1 − J ) ©
∂V (x, z)
ª
(W (x, z))u−1 dx ®
­1 +
u−1
∂x
«
¬
0
∫bz c 
 u−1
©
ª
1
m−1−x
­ 1 − m−1
®
dx
m−1
­
®
­
®
0
u(1−J ) ­
®
= 1 − u−1 ­
®
m
∫

 u−1 ®
­
(m−x )(m−1−z)
­− 1
dx ®®
­ m−1
(m−1)(m−z)
«
¬
bz c+1
=1−

W (x, z) := P(h j (d) > x | d , d 0 ∧ hk (d 0 ) = z)
= P(h j (d) > x | hk (d) > hk (d 0 ) ∧ hk (d 0 ) = z)
= P(h j (d) > x | hk (d) > z ∧ hk (d 0 ) = z)
= P(h j (d) > x | hk (d) > z)
∫m
1
P(h j (d) > x | hk (d) = z 0 )dz 0
=
m −z
z

5

h
 u i bz c
© 1 + u1 m−1−x
ª
m−1
®
u(1−J ) ­
x =0
= 1 − u−1 ­
®
­ 1  m−1−z  u−1  m−x  u  m
®
+ u m−z
m−1
x
=
bz
c+1
«
¬

u
1 m−1− bz c
1
1
+
−
ª
u
m−1
u
u(1−J ) ©
= 1 − u−1 ­­

 u−1 
 u ®®
m−1− bz c
− u1 m−1−z
m−z
m−1
«
¬



u
u−1 
(1−J ) m−1− bz c
= J − u−1
1 − m−1−z
.
m−1
m−z

The last step used (17) for the case j , k.
Now we are finally able to derive the variance of the Jaccard
index estimator (3)
m−1
1
©Õ
ª
Var ­
I (h j (A) = h j (B))®
2
m
« j=0
¬
m−1
m−1
Õ
Õ
1
Cov(I (h j (A) = h j (B)), I (hk (A) = hk (B)))
= 2
m j=0
k =0


J (1 − J )
1 − α(m, u)
=
m
−
m
(m
−
1)
m−1
m2
J (1 − J )
=
α(m, u).
m

Var( Jˆ) =

(16)

Now we can insert (11) and (16) into (10) which gives
P(h j (A) = h j (B) | hk (A) = hk (B))
∫m
=
R 0 (z)S(z)dz

REFERENCES
[1] A. Z. Broder. 1997. On the Resemblance and Containment of Documents. In
Proceedings of the Compression and Complexity of Sequences. 21–29.
[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. 2009. Introduction to
Algorithms. MIT Press.
[3] S. Dahlgaard, M. B. T. Knudsen, and M. Thorup. 2017. Fast Similarity Sketching.
(2017). arXiv:1704.04370
[4] R. A. Fisher and F. Yates. 1938. Statistical Tables for Biological, Agricultural and
Medical Research. Oliver & Boyd, London.
[5] P. Li, A. Owen, and C. Zhang. 2012. One Permutation Hashing. Advances in
Neural Information Processing Systems 25 (2012), 3113–3121.
[6] J. Lumbroso. 2013. Optimal Discrete Uniform Generation from Coin Flips, and
Applications. (2013). arXiv:1304.1916
[7] A. Shrivastava. 2017. Optimal Densification for Fast and Accurate Minwise
Hashing. (2017). arXiv:1703.04664
[8] A. Shrivastava and P. Li. 2014. Densifying One Permutation Hashing via Rotation
for Fast Near Neighbor Search. In Proceedings of the 31st International Conference
on Machine Learning. 557–565.
[9] A. Shrivastava and P. Li. 2014. Improved Densification of One Permutation
Hashing. (2014). arXiv:1406.4784
[10] W. Stadje. 1990. The Collector’s Problem with Group Drawings. Advances in
Applied Probability 22, 4 (1990), 866–882.

0

=J−

∫m

R 0 (z) (J − S(z)) dz

0

=J−

l +1
m−1
Õ∫

R 0 (z) (J − S(z)) dz

l =0 l
l +1

m−1 ∫
u Õ
=J− u
(m − z)u−1 (J − S(z)) dz
m
l =0 l

1−J
= J − muu u−1

1−J
= J − muu u−1

=J−
=J−
=J−

(1−J )

l +1
m−1
Õ ∫ © (m

­
­
­
l =0 l
«

m−2
Õ
l =0

Ím−2
l =0



m−1−l
m−1


u
− z)u−1 m−1−l
·ª
m−1
®


u−1  ® dz
®
m−1−z
· 1 − m−z
¬
!
l +1
∫
u−1

(m − z)
u

l

− (m − 1 − z)u−1

(m−1−l )u ((m−l )u +(m−2−l )u −2(m−1−l )u )
(m−1)u m u (u−1)

l u ((l +1)u +(l −1)u −2l u )
(m−1)u m u (u−1)
(1−J )(1−α (m,u))
.
m−1
(1−J )

dz

Ím−1
l =1

(17)

Here we introduced α(m, u) as defined in (7).
To calculate the variance of the Jaccard index estimator we need
the covariance of indicators I (h j (A) = h j (B)) and I (hk (A) = hk (B))
Cov(I (h j (A) = h j (B)), I (hk (A) = hk (B)))
= E(I (h j (A) = h j (B))I (hk (A) = hk (B)))
− E(I (h j (A) = h j (B))) E(I (hk (A) = hk (B)))
= P(h j (A) = h j (B) ∧ hk (A) = hk (B))
− P(h j (A) = h j (B))P(hk (A) = hk (B))
= P(h j (A) = h j (B) | hk (A) = hk (B)) P(hk (A) = hk (B)) − J 2
= P(h j (A) = h j (B) | hk (A) = hk (B)) J − J 2
(
1
j =k
= J (1 − J ) ·
1−α (m,u)
− m−1
j , k.
6

