HyperMinHash: MinHash in LogLog space
∗

arXiv:1710.08436v3 [] 28 Mar 2018

Yun William Yu

Griffin M. Weber

Harvard Medical School DBMI
10 Shattuck St #3
Boston, Massachusetts 02139

Harvard Medical School DBMI
10 Shattuck St #3
Boston, Massachusetts 02139

william yu@hms.harvard.edu

griffin weber@hms.harvard.edu

ABSTRACT

1, 16, 2]. However, to our knowledge, there are no practical sub-logarithmic sketches to replace MinHash for all its
features.

In this extended abstract, we describe and analyse a streaming probabilistic sketch, HYPERMINHASH, to estimate the
Jaccard index (or Jaccard similarity coefficient) over two
sets A and B. HyperMinHash can be thought of as a compression of standard log n-space MinHash by building off of a
HyperLogLog count-distinct sketch. For a multiplicative approximation error 1+ on a Jaccard index t, given a random

1
oracle, HyperMinHash needs O −2 log log n + log t
space. Unlike comparable Jaccard index fingerprinting
algorithms (such as b-bit MinHash, which uses less space),
HyperMinHash retains MinHash’s features of streaming
updates, unions, and cardinality estimation. Our new
algorithm allows estimating Jaccard indices of 0.01 for set
cardinalities on the order of 1019 with relative error of
around 10% using 64KiB of memory; MinHash can only
estimate Jaccard indices for cardinalities of 1010 with the
same memory consumption. Note that we will operate
in the unbounded data stream model and assume both a
random oracle and shared randomness.

1.

1.1

MinHash

Given two sets A and B, where |A| = n and |B| = m,
and n > m without loss of generality, the Jaccard index is
defined as
|A ∩ B|
.
(1)
t(X, Y ) =
|A ∪ B|
Clearly, if paired with a good count-distinct union estimator for |A ∪ B|, this allows us to estimate intersection sizes
as well. Though Jaccard originally defined this index to
measure ecological diversity in 1902 [14], in more modern
times, it has been used as a proxy for the document similarity problems. In 1997, Broder introduced min-wise hashing (colloquially known as ‘MinHash’) [4], a technique for
quickly estimating the resemblance of documents by looking at the Jaccard index of ‘shingles’ (collections of phrases)
contained within the documents.
MinHash Jaccard-index estimation relies on a simple fact:
if you apply a random permutation to the universe of elements, the chance that the smallest items under this permutation in sets A and B are the same is precisely the Jaccard index. To see this, consider a random permutation of
A ∪ B. The minimum element will come from either A \ B,
B \ A, or A ∩ B, all disjoint sets. If the minimum element
lies in A \ B, then min(A) 6∈ B, so min(A) 6= min(B); the
same is of course true by symmetry for B \ A. Conversely,
if min(A ∪ B) ∈ A ∩ B, then clearly min(A) = min(B).
Because the permutation is random, every element has an
equal probability of being the minimum, and thus

INTRODUCTION

Many questions in data science can be rephrased in terms
of the number of items in a database that satisfy some
Boolean formula. For example, “how many participants in
a political survey are independent and have a favorable view
of the federal government?”, or “how many of the source IPs
used in a DDoS attack today were also used last month?” In
this paper, we consider the design of approximate streaming
sketches to answer questions phrased in conjunctive normal
form (an AND of ORs); this is of course equivalent to estimating the cardinality of intersections of unions of a collection of sets.
The standard technique used by industry to answer these
questions is the MinHash sketch [4], which uses O(−2 log n)
space, allows streaming updates, and approximates both the
union cardinality and Jaccard index [14], a proxy for set
similarity that when coupled with union cardinality, allows
estimation of intersection sizes. The literature already has
sub-logarithmic near-optimal probabilistic data structures
for approximating the ‘count-distinct’ problem [3, 7, 12, 13,
15], which is equivalent to finding the cardinality of unions
of sets (i.e. ORs in CNF). Similarly, sub-logarithmic nearoptimal fingerprints exist for computing Jaccard index[14,

P (min(A) = min(B)) =

|A ∩ B|
.
|A ∪ B|

(2)

While using a single random permutation produces an
unbiased estimator of t(X, Y ), it is a Bernouli 0/1 random
variable with high variance. So, instead of using a single
permutation, one averages k trials. The expected fraction of
matches is also an unbiased estimator of the Jaccard index,
but with variance decreased by a factor of 1/k.
Though the theoretical justification is predicated on having a true random permutation, in practice we approximate
that by using good random hash functions instead. A good
hash function will specify a nearly total ordering on the universe of items, and provided we use θ(log(n)) bits for the
hash function output, the probability of accidental collision
of min-hashes is exponentially small.

∗Corresponding author
1

Though theoretically easy to analyze, this scheme has a
number of drawbacks, chief amongst them the requirement
of having k random hash functions, which means that the
computational complexity is θ(nk) to generate the sketch.
To address this, several variants of MinHash have been proposed [5]:

under the assumptions of shared randomness and that standard cryptographic hash functions (e.g. SHA-1) behave as
random oracles.

1.3

1. k-hash functions. The scheme described above,
which has the shortcoming of using θ(nk) computation
to generate the sketch.
2. k-minimum values. A single hash function is used,
but instead of storing the single minimum value, we
store the smallest k values for each set (also known
as the KMV sketch [3]). Sketch generation time is
reduced to O(n log k), but we also incur an O(k log k)
sorting penalty when computing Jaccard index.
3. k-partition. Another 1-permutation MinHash variant, k-partition stochastically averages by first deterministically partitioning a set into k parts using the
first couple bits of the hash value, and then stores the
minimum value in each partition [17]. k-partition has
the advantage of O(n) sketch generation time and O(k)
Jaccard index computation time, at the cost of some
difficulty in the analysis.
It is important here to remark that for all of the above
variants, MinHash sketches of A and B can be losslessly
combined to form the MinHash sketch of A ∪ B. Using order statistics, it is additionally possible to estimate the union
cardinalities from the sketch [3], so we can directly estimate
intersection size in addition to Jaccard index. This also implies that streaming updates are permitted, so preprocessing
incurs no additional space requirement.

1.2

Jaccard index fingerprints

We aim to similarly reduce space-complexity for MinHash,
while preserving all of its features; we focus here on Jaccard
index in the unbounded data stream model. As a preliminary, we note that as with the count-distinct problem, much
theoretical work has focused on reducing the amount of randomness needed by MinHash to only requiring k-min-wise
(or k − d-min-wise) independent hash functions [10, 19, 11].
In this extended abstract, we will however again assume the
setting of shared randomness and the existence of a random oracle, which is standard in industry practice. In the
discussion, we will return to this point and mention several
relevant techniques.
First we note that trivially, HyperLogLog union cardinalities can be used to compute intersection cardinalities and
thus Jaccard indexes using the inclusion-exclusion principle. Unfortunately, the relative error is then in the size of
the union (as opposed to the size of the Jaccard index for
MinHash) and compounds when taking the intersections of
multiple sets; for small intersections, the error is often too
great to be practically feasible, unless significantly more bits
are used. More precisely, in order to achieve the same relative error, the number of bits needed when using inclusionexclusion scales with the square of the inverse Jaccard index, as opposed to scaling with just the inverse Jaccard index (Table 1 of [18]). Notably, some newer cardinality estimation methods based on maximum-likelihood estimation
are able to more directly access intersection sizes in HyperLogLog sketches, which can then be paired with unioncardinality to estimate Jaccard index [8, 9]. However, this
approach, while more sophisticated, is restricted to the information available in the HyperLogLog sketch itself, and
seems empirically to be a constant order (< 3x) improvement over conventional inclusion-exclusion.
Alternately, when unions and streaming updates are not
necessary, the literature provides many examples of Jaccard
index fingerprints in better than log-space [1, 16, 2]. Stateof-the-art fingerprinting methods based on either reduction
to F2 -norm sketching or truncating bits of MinHash (‘b-bit
MinHash’) are able to achieve space
bounds of O(−2 ) in


Count-distinct union cardinality

All of the standard variants of MinHash given in the last
section use logarithmic bits per bucket in order to prevent
accidental collisions (i.e. we want to ensure that when two
hashes match, they came from identical elements), though in
the case of k-partition, some of those bits can be stored implicitly in the bucket identity. However, in the related problem of cardinality estimation of unique items (the ‘countdistinct’ problem), literature over the last several decades
produced several streaming sketches that require less than
logarithmic bits per bucket. Indeed, the LogLog, SuperLogLog, and HyperLogLog family of sketches requries, as
given in the name, only log log(n) bits per bucket by storing
only the position of the first 1 bit of a uniform hash function,
thus requiring O(−2 log log n) bits to store the hashes [7, 12,
13]. Notably these methods all require access to a random
oracle (i.e. a truly random hash function), and storing such
hash functions requires an additional log n bits of space, for
a total of O(−2 log log n + log n) space. Further compacting
of the hashes by use of concentration inequalities, and use
of k-min-wise independent hash functions allowed both relaxing the requirement of a random oracle, and reduction of
the space-complexity to O(−2 + log n) (or without counting the hash function, O(−2 + log log n) in the setting of
shared randomness) [15], resulting in an essentially optimal
sketch requiring only constant bits per bucket. In practice
though, the double logarithmic HyperLogLog sketch is used

the general problem [1, 16] and O

(1−t)2
2

log

1
1−t

for highly

similar streams when the Jaccard index t is large [2]. For
estimating the Jaccard similarity between exactly two sets,
these fingerprinting techniques are basically asymptotically
optimal [18].

1.4

sub-logarithmic MinHash

However, b-bit MinHash and F2 -norm reductions, while
great for Jaccard index, lose many of the benefits of standard MinHash, even just for Jaccard index estimation. Because b-bit MinHash only takes the lowest order b bits of
the minimum hash value after finding the minimum, it also
requires log(n) bits per bucket during the sketch generation
phase, the same as standard MinHash. This also implies
that sketches cannot be merged together, so union cardinalities cannot be estimated. The same holds true for F2 -norm
reductions because of double counting shared items.
Some of these shortcomings can be overcome by pairing
a Jaccard index fingerprint with a sub-logarithmic count2

distinct sketch. When combined, this allows for accurate estimation of intersection sizes, not just Jaccard index. However, this still does not permit the usage of unions or streaming updates, so more complex predicates (e.g. |(A ∪ B) ∩ C|)
still cannot be evaluated.
We resolved this issue by building a new sketch, HyperMinHash, as a hybrid between HyperLogLog and k-partition
MinHash. Using HyperLogLog as a scaffold for other statistics of interest has been previously suggested for concave
sublinear frequency statistics, but not for MinHash [6]. HyperMinHash as we describe below requires



1
O −2 log log n + log
t

(Figure 3). An explicit exact formula for the expected number of collisions is
r
n 
n 
−1 
∞ 2X
X
2r + j + 1
2r + j
− 1−
·
EC =
1 − i+r
2
2i+r
i=1 j=0
m 
m 

2r + j + 1
2r + j
− 1−
,
1 − i+r
2
2i+r
(3)
though finding a closed formula is rather more difficult.
Intuitively, suppose that our hash value is (12, 01011101)
for partition 01. This implies that the original bitstring
of the minimum hash was 0.0100000000000101011101 · · · .
Then a uniform random hash in [0, 1] collides with this number with probability 2−(2+12+8) = 2−21 . So we expect to
need cardinalities on the order of 221 before having many
collisions. Luckily, as the cardinalities of A and B increase,
so does the expected value of the leading 1 in the bitstring,
as analyzed in the construction of HyperLogLog [13]. Thus,
the collision probabilities remain roughly constant as cardinalities increase, at least until we reach the precision limit
of the LogLog counters.
But of course, we store only a finite number of bits for
the leading 1 indicator (often 6 bits). Because it’s a LogLog
counter, storing 6 bits is sufficient for set cardinalities up to
6
O(22 = 264 ). This increases our collision surface though, as
we might have collisions in the lower left region near the origin (Figure 4). We can directly compute the collision probability (and similarly the variance) by summing together the
probability mass in these boxes, replacing the infinite sum
with a finite sum (Lemma 4). For more sensitive estimations, we can subtract the expected number of collisions to
debias the estimation. In the next section we will prove
bounds on the expectation and variance in the number of
collisions.

space and has all of the standard nice features of MinHash,
including streaming updates, the ability to take unions of
sketches, and count-distinct cardinality estimation. Though
this construction is not space optimal—e.g. we could very
likely drop in the KNW sketch [15] instead of HyperLogLog
[13] for a space-reduction—it is a practical compromise and
easy to implement in software.

2.

HYPERMINHASH

MinHash works under the premise that two sets will have
identical minimum value with probability equal to the Jaccard distance, because they can only share a minimum value
if that minimum value corresponds to a member of the intersection of those two sets. If we have a total ordering on the
union of both sets, the fraction of equal buckets is an unbiased estimator for Jaccard distance. However, with limited
precision hash functions, there is some chance of accidental
collision, when the value does not correspond to a member
of the intersection. In order to get close to a true total ordering, the space of potential hashes must be on the order of
the size of the union, and thus we must store O(log n) bits.
Note, however, that the minimum of of a collection of
uniform [0, 1] random variables X1 , . . . , Xn is much more
likely to be a small number than a large one (the insight
behind most count-distinct sketches [3]). HyperMinHash
operates identically to MinHash, but instead of storing the
minimum values with fixed precision, it effectively uses an
adaptive precision that increases resolution when the values
are smaller by using initial loglog counters (from LogLog
cardinality estimation) and then storing a fixed number of
bits beyond that (similar in spirit to b-bit MinHash). More
precisely, after dividing up the items into k partitions, we
store the position of the leading 1 bit in the first 2q bits
(and store 2q + 1 if there is no 1 bit in the first 2q bits),
and r bits following that (Figure 1). We do not need a total
ordering so long as the number of accidental collisions in the
minimum values is low.
To analyze the performance of HyperMinHash compared
to random-permutation MinHash (or equivalently 0-collision
standard MinHash) it suffices to consider the expected number of accidental collisions. We first describe an intuitive
analysis before proving things rigorously. Here, we will also
only analyze the simple case of collisions while using only
a single bucket, but the same flavor of argument holds for
multiple partitions. The HyperLogLog part of the sketch
results in collisions whenever two items match in order of
magnitude (Figure 2).
By pairing it with an additional r-bit hash, our collision
space is narrowed by a factor of about 2r within each bucket

3.

PROOFS

The main result of this paper bounds the expectation and
variance of accidental collision, given two HyperMinHash
sketches of disjoint sets. First, we rigorously define the full
HyperMinHash sketch.
Definition 1. We will define fp,q,r (A) : S → {{1, . . . , 2q } ×
p
{0, 1}r }2 to be the HyperMinHash sketch constructed from
Figure 1, where A is a set of hashable objects and p, q, r ∈ N,
and let fp,q,r (A)i : S → {1, . . . , 2q } × {0, 1}r be the value of
the ith bucket in the sketch.
More precisely, let h(x) : S → [0, 1] be a uniformly random
q
hash function. Let ρq (x) = min
let
 (b− log2 (x)c
 + 1, 2 ),
σr (x) = bx2r c, and let ĥq,r (x) = ρq (x), σr x2ρq (x) − 1
Then, we will define


fp,q,r (A)i = ĥq,r 

min

a∈A
i2−p <h(a)<(i+1)2−p

.

(h(a)2p − i) .

Definition 2. Let A, B be hashable sets with |A| = n, |B| =
m, n > m, and A∩B = ∅. Then define an indicator variable
for collisions in bucket i of their respective HyperMinHash
sketches
Zp,q,r (A, B, i) = 1(fp,q,r (A)i =fp,q,r (B)i ) .
3

(4)

Objects in Set
♣
◪
▣
◊
✪
☼
⚂
⟁
⧩
⭔
♫
♾
⌬
⌲
⏣
♡
✠
⚲

Hashed values
0.001100110100⋯
0.100110111111⋯
0.101011111011⋯
0.000101110010⋯
0.011000111010⋯
0.000110100011⋯
0.101100011011⋯
0.010001100100⋯
0.111001000111⋯
0.011001101000⋯
0.100010001110⋯
0.100010111100⋯
0.101101011010⋯
0.110011011110⋯
0.111000011100⋯
0.000011000011⋯
0.010010000000⋯
0.110000011101⋯

Partition 00
0.001100110100⋯
0.000101110010⋯
0.000110100011⋯
0.000011000011⋯

Minimum of 𝑃00
0.000011000011⋯
(3, 1000)

Partition 01
0.011000111010⋯
0.010001100100⋯
0.011001101000⋯
0.010010000000⋯

Minimum of 𝑃01
0.010001100100⋯
(4, 1001)

Partition 10
0.100110111111⋯
0.101011111011⋯
0.101100011011⋯
0.100010001110⋯
0.100010111100⋯
0.101101011010⋯
Partition 11
0.111001000111⋯
0.110011011110⋯
0.111000011100⋯
0.110000011101⋯

Minimum of 𝑃10
0.100010001110⋯
(3, 0001)

Partition
00
01
10
11

Hash
(3, 1000)
(4, 1001)
(3, 0001)
(5, 0111)

Minimum of 𝑃11
0.110000011101⋯
(5, 0111)

Figure 1: HyperMinHash generates sketches in the same fashion as one-permutation MinHash. It begins by hashing each
object in the set to a uniformly random number between 0 and 1, encoded in binary. Then, the hashed values are partitioned
by the first p, and the minimum value within each partition is taken. Each value is specified by a tuple; the first part is the
position of the leftmost 1 in the first 2q bits, and 2q + 1 otherwise, so exactly identical to a HyperLogLog sketch. The second
part is the value of the next r bits in the bitstring. Note that this is mathematically equivalent to applying three independent
hash functions for each bucket for the green, blue, and red bits, or, alternately, to using a single hash function but dividing
the bitstring into fixed-length regions first.

Our main theorems follow:
P2p −1
Theorem 1. C =
i=0 Zp,q,r (A, B, i) is the number of
collisions between the HyperMinHash sketches of two disjoint
sets A and B. Then the expectation


5
n
EC ≤ 2p
+
.
(5)
q
2r
2p+2 +r

pdf of min(Y1 , . . . , Ym )

1

Theorem 2. Given the same setup as in Theorem 1,
leftmost 1 indicator

Var(C) ≤ E[C]2 + E[C].

(0,0)

Theorem 1 allows us to correct for the number of random
collisions before computing Jaccard distance, and Theorem
2 tells us that the standard deviation in the number of collisions is approximately the expectation.
We will first start by proving a simpler proposition.
Proposition 3. Consider a HyperMinHash sketch with only
1 bucket on two disjoint sets A and B. i.e. f0,q,r (A) and
f0,q,r (B). Let γ(n, m) ∼ Z0,q,r (A, B, 0). Naturally, as a
good hash function results in uniform random variables, γ is
only dependent on the cardinalities n and m. We claim that

1
pdf of min(X1 , . . . , Xn )

Eγ(n, m) ≤
Figure 2: HyperLogLog sections, used alone, result in collisions whenever the minhashes match in order of magnitude.

n
6
+ 2q +r .
2r
2

(6)

Proving this will require a few technical lemmas, which
we’ll then use to prove the main theorems.
4

pdf of min(Y1 , . . . , Ym )

pdf of min(Y1 , . . . , Ym )

2r subbuckets

1

2r subbuckets

1
0.111

leftmost 1 indicator

leftmost 1 indicator

0.110
0.101
0.100
0.0111
0.0110
0.0101

(0,0)

0.0100
0.00111
0.00110
0.00101
0.00100
0.00011
0.00010
0.00001
0.00000

1

precision limit =

2r subbuckets

pdf of min(X1 , . . . , Xn )

Figure 3: HyperMinHash further subdivides HyperLogLog
leading 1-indicator buckets, achieving a much smaller collision space, so long as we precisely store the position of the
leading 1.

1
q
22

1
pdf of min(X1 , . . . , Xn )

Figure 4: In practice, HyperMinHash has a limited number
of bits for the loglog counters, so there’s a final lower left
bucket at the precision limit.

The probability mass enclosed in a square along the diagonal
S = [s1 , s2 ]2 ⊂ [0, 1]2 is then precisely
Z s2 Z s2
µ(S) =
n(1 − x)n m(1 − y)m dydx

Lemma 4.
Eγ(n, m) =

P(f0,q,r (A)0 = f0,q,r (B)0 )
n 
n 
2r + j + 1
2r + j
− 1−
·
1 − r+i
=
2
2r+i
i=1 j=0

m 
m 
2r + j
2r + j + 1
1 − r+i
− 1−
2
2r+i
q 2r −1 
n 
n 
2
X
X
j+1
j
− 1 − r+i−1
·
+
1 − r+i−1
2
2
i=2q j=0

m 
m 
j
j+1
1 − r+i−1
− 1 − r+i−1
2
2
q
r
2X
−1 2X
−1 

s1

s1

= [(1 − s2 )n − (1 − s1 )n ] [(1 − s2 )m − (1 − s1 )m ] (7)
Recall f0,q,r (A)0 ∈ {1, . . . , 2q } × [0, 1]r ≡ {1, . . . , 2q } ×
{0, . . . , 2r − 1}, so given f0,q,r (A)0 = (i, j), x = 0.00 0i 1j · · ·
in the binary expansion, unless i = 2q , in which case the
0 i
binary expansion is x = 0.0
0 j · · · . rThat in turn gives
r
+j
, s2 = 2 2+j+1
when i < 2q ,
s1 < x < s2 , where s1 = 22r+i
r+i
j
j+1
and s1 = 2r+i−1 , s2 = 2r+i−1 . Collisions happen precisely
when s1 < x, y < s2 .
Finally, using the s1 , s2 formulas above, it suffices to sum
the probability of collision over the image of f , so
q

Proof. Let a1 , . . . , an be random variables corresponding to
the hashed values of items in A. Then ai ∈ [0, 1] are uniform r.v. Similarly, b1 , . . . , bm , drawn from hashed values
of B are uniform [0, 1] r.v. Let x = min{a1 , . . . , an } and
y = min{b1 , . . . , bm }. Then we have probability density
functions

Eγ(n, m) =

r

−1
2 2X
X

µ([s1 , s2 ]).

(8)

i=1 j=0

Substituting in for s1 , s2 , and µ completes the proof. Note
also that this is precisely the sum of the probability mass
in the red and purple squares along the diagonal in Figure
4.

pdf(x) = n(1 − x)n , for x ∈ [0, 1],
pdf(y) = m(1 − y)m , for y ∈ [0, 1]

While Lemma 4 allows us to explicitly compute Eγ(m, n),
the lack of a closed form solution makes reasoning about
it difficult. Here, we will upper bound the expectation by
integrating over four regions of the unit square that cover
all the collision boxes (Figure 5). For ease of notation, let
q
r̄ = 2r and q̄ = 22 .

and cumulative density functions
cdf(x) = 1 − (1 − x)n , for x ∈ [0, 1],
cdf(y) = 1 − (1 − y)m , for y ∈ [0, 1].
We are particularly interested in the joint probability density function
n

m

r̄
• The Top Right box T R = [ r̄ +1
, 1]2 (in orange in Figure 5).

2

pdf(x, y) = n(1 − x) m(1 − y) , for (x, y) ∈ [0, 1] .
5

For n, m < r̄ q̄, we note that the linear binomial approximation is actually a strict upper bound (trivially verified
n
through the Taylor expansion), so µ(BL) ≤ r̄nm
2 q̄2 ≤ r̄ q̄ .

pdf of min(Y1 , . . . , Ym )

1

Lemma 7. The probability mass of the ray from the origin
can be bounded µ(RAY ) ≤ 3r̄ .

0.111
0.110

Top Right

Proof. Unfortunately, the ray is not aligned to the axes, so
we cannot integrate x and y separately.
Z r̄ Z r̄ +1 x
r̄ +1
r̄
µ(RAY ) =
n(1 − x)n−1 m(1 − y)m−1 dydx

0.101
0.100
0.0110

r̄ x
r̄ +1

0

Magenta Ray

0.0111
Black Strip

r̄
r̄ +1

Z
=

0.0101

n(1 − x)n−1


1−

0

0.0100
0.00111
0.00110
0.00101
0.00100
0.00011
0.00010
0.00001
0.00000

m 
m 
r̄ +1
r̄
− 1−
x
x
dx
r̄ +1
r̄

Using the elementary difference of powers formula, note that
for 0 ≤ α ≤ β ≤ 1,
!
m
X
m
m
m−i i−1
α − β = (α − β)
α
β
≤ (α − β)mβ m−1 .

Bottom Left
1
pdf of min(X1 , . . . , Xn )

i=1

With a bit of symbolic manipulation, we can conclude that
Figure 5: We’ll upper bound the collision probability of hyperminhash by dividing it into these four regions of integration: (a) the Top Right orange box, (b), the magenta ray
covering intermediate boxes, (c) the black strip covering all
but the final purple box, and (d) the final purple subbucket
by the origin.

µ(RAY )
"

m−1 #
Z r̄
r̄ +1
r̄
2 r̄ +1
n−1
≤
xm 1 −
x
dx
n(1 − x)
r̄(l + 1)
r̄ +1
0

n+m−2
Z r̄
r̄ +1
r̄
2 r̄ +1
≤
nm 1 −
xdx.
r̄(l + 1) 0
r̄ +1

• The magenta triangle from the origin bounded by the
r̄
r̄
x and y = r̄ +1
x with 0 < x < r̄ +1
, which
lines y = r̄ +1
r̄
we will denote RAY .

With a straight-forward integration by parts,
µ(RAY )
n+m−1
r̄ 2
(r̄ +1)2

n+m−1
r̄ +1
1
r̄ 2
2 r̄ +1
nm
·
−
·
·
1
−
r̄ 2
r̄
n+m−1
n+m
(r̄ +1)2
2 r̄ +1
r̄ +1
1
nm
+
·
·
·
r̄ 2
r̄
n+m−1
n+m
(2 r̄ +1)(r̄ +1)
nm
3
·
≤ .
≤
r̄ 3
r̄
(n + m)(n + m − 1)

• The black strip near the origin covering all the purple
boxes except the one on the origin, bounded by the
lines y = x − r̄1q̄ , y = x + r̄1q̄ , and r̄1q̄ < x < 1q̄ , which
we will denote ST RIP .
• The Bottom Left purple box BL = [0,

≤−

1 2
] .
r̄ q̄

Lemma 5. The probability mass contained in the top right
square µ(T R) ≤ 1r̄ .
Proof. By Equation 7,
Z 1 Z 1
µ(T R) =
n(1 − x)n−1 m(1 − y)m−1 dydx
r̄
r̄ +1

r̄ +1

=

r̄ +1

Proof. Using the same integration procedure and difference
of powers formula used in the proof of Lemma 7,
Z 1 Z x+ 1
q̄
r̄ q̄
µ(ST RIP ) =
n(1 − x)n−1 m(1 − y)m−1 dydx

1
1
≤ .
(r̄ +1)n+m
r̄

1
r̄ q̄

Lemma 6. The probability mass contained in the bottom
left square near the origin is µ(BL) ≤ r̄nq̄ .

≤

Proof.
1
r̄ q̄

Z
µ(BL) =
0

1
r̄ q̄

Z

=
n−1

n(1 − x)

m(1 − y)

m−1


1−

Lemma 8. The probability mass of the diagonal strip near
the origin is µ(ST RIP ) ≤ 2r̄ .

r̄
r̄ +1

= [−(1 − x)n ]1 r̄ [−(1 − y)m ]1 r̄

r̄
2 r̄ +1
nm
·
·
r̄ 2
n + m − 1 r̄ +1

dydx

2
r̄ q̄

x− r̄1q̄

Z

1
q̄
1
r̄ q̄


n+m−2
1
nm 1 − x +
r̄ q̄

2
nm
r̄ −1
2
·
·
≤ .
r̄ q̄ n + m − 1 r̄ q̄
r̄

0
1
r̄ q̄

1
r̄ q̄

= [−(1 − x)n ]0 [−(1 − y)m ]0


n  

m 
1
1
= 1− 1−
1− 1−
.
r̄ q̄
r̄ q̄

Proof of Proposition 3. Summing bounds from Lemmas 5,
6, 7, and 8, Eγ(n, m) ≤ 6r̄ + r̄nq̄ = 26r + 22qn+r .
6

Figure 6: For a fixed size sketch, HyperMinHash has better accuracy and/or cardinality range than MinHash.
We compare Jaccard index estimation for identically sized sets with Jaccard index of 1/3 (i.e. 50% overlap), so the maximum
relative error is 2, and plot the mean relative errors without estimated collision correction. (green circle) A 256 byte HyperMinHash sketch, with 256 buckets of 8 bits each, 4 bits of which are allocated to the LogLog counter, Jaccard index estimation
remains stable until cardinalities around 223 . (orange diamond) A 256 byte MinHash sketch with 256 buckets of 8 bits each
achieves similar accuracy at low cardinalities, but fails once cardinalities approach 214 . (blue triangle) A 256 byte MinHash
sketch with 128 buckets of 16 bits can access larger cardinalities of around 220 , but to do so trades off on low-cardinality
accuracy.

Var(C) =

Proof of Theorem 1. Let Ai , Bi be the ith partitions of A
and B respectively.
ease of notation, let’s define p̄ = 2p .
PFor
p̄−1
Recall that C =
j=0 Zp,q,r (A, B, j). We will first bound
EZp,q,r (A, B, j) using the same techniques used in Proposition 3. Notice first that Zp,q,r (A, B, j) effectively rescales
the minimum hash values from Z0,q,r (A, B, j) = γ(n, m)
down by a factor of 2p ; i.e. we scale down both the axes
in Figure 5 by substituting q̄ ← q̄ p̄ in Lemmas 8 and 6.
We do not need Lemma 5 because its box is already covered by the Magenta Ray from Lemma 7, which we do
not scale. Summing these together, we readily conclude
EZp,q,r (A, B, j) ≤ 5r̄ + r̄ nq̄ p̄ = 25r + 2p+2nq +r . Then by lin

earity of expectation, EC ≤ 2p 25r + 2p+2nq +r .

X

∀i,|Bi |=βi

Cov

1α̊1 ,β̊1 Z̊ j1 α̊1 , β̊1 , 1α̊2 ,β̊2 Z̊ j2 α̊2 , β̊2











α̊1 ,β̊1 j1 ,j2 =0
α̊2 ,β̊2

But note that for (α̊1 , β̊1 ) 6= (α̊2 , β̊2 ), 1α̊1 ,β̊1 = 1 =⇒
1α̊2 ,β̊2 = 0 and vice versa, because they are disjoint indicator
variables. As such, for (α̊1 , β̊1 ) 6= (α̊2 , β̊2 ),





Cov 1α̊1 ,β̊1 Z̊ j1 α̊1 , β̊1 , 1α̊2 ,β̊2 Z̊ j2 α̊2 , β̊2
≤ 0,
implying that

Proof of Theorem 2. By conditioning on the multinomial
distribution, we can decompose C into


p̄−1
X
X
|Ai |=αi


C=
1 ∀i,|Ai |=αi
Zp,q,r A, B, j |Bi |=βi .
α1 +···αp̄ =n
β1 +···βp̄ =m

p̄−1
X

Var(C)
≤

p̄−1
X X

Cov



1α̊,β̊ Z̊ j1 α̊, β̊ , 1α̊,β̊ Z̊ j2 α̊, β̊








α̊,β̊ j1 ,j2 =0

i=0

=

For ease of notation in the following, we will use α̊, β̊
to denote the event ∀i, |Ai | = αi and ∀i, |Bi | = βj respectively. Additionally,
Z̊(j) = Zp,q,r (A, B, j). So,
 let 
P
Pp̄−1
C = α̊,β̊ j=0 1α̊,β̊ Z̊ j α̊, β̊ .
Then

p̄−1
XX

Var



1α̊,β̊ Z̊ j α̊, β̊




α̊,β̊ j=0

+

7

X

X

α̊,β̊

j1 6=j2
0≤j1 ≤p̄−1
0≤j2 ≤p̄−1

Cov

1α̊,β̊ Z̊ j1 α̊, β̊ , 1α̊,β̊ Z̊ j2 α̊, β̊











.

.

4.

Note that the first term can be simplified, recalling that
Z̊ is a {0,1} Bernouli r.v., so

For completeness, we give experimental validation for
the behavior of Jaccard index estimation on raw (Hyper)MinHash sketches with no expected error collision.
In Figure 6, we allocate 256 bytes for two standard
MinHash sketch and a HyperMinHash sketch. For fixed
sketch size and cardinality range, HyperMinHash is more
accurate; or, for fixed sketch size and bucket number,
HyperMinHash can access exponentially larger set cardinalities. Pseudocode and a Python implementation are
available respectively in the appendix and on Github
(https://github.com/yunwilliamyu/hyperminhash).

p̄−1



X
Var 1α̊,β̊ Z̊ j α̊, β̊


j=0

=

p̄−1
X

p̄−1

 X
h
i
Var Z̊ (j) ≤
E Z̊ (j) = EC.

j=0

j=0

Moving on, from the covariance formula, for independent
random variables X1 , X2 , Y ,
Cov(X1 Y, X2 Y ) = E[X1 X2 Y 2 ] − E[X1 Y ]E[X2 Y ]

= E[X1 ]E[X2 ] E[Y 2 ] − E[Y ]2

5.

Thus the second term of the summation can be bounded as
follows:





X X
Cov 1α̊,β̊ Z̊ j1 α̊, β̊ , 1α̊,β̊ Z̊ j2 α̊, β̊

=

≤

j1 6=j2
0≤j1 ≤p̄−1
0≤j2 ≤p̄−1

X

X

α̊,β̊

j1 6=j2
0≤j1 ≤p̄−1
0≤j2 ≤p̄−1

p̄−1 p̄−1
XX
X

h 
i h 
i


E Z̊ j1 α̊, β̊ E Z̊ j2 α̊, β̊ Var 1α̊,β̊

h 
i h 
i


E Z̊ j1 α̊, β̊ E Z̊ j2 α̊, β̊ Var 1α̊,β̊

α̊,β̊ j1 =0 j2 =0

=

X

=

X

≤

X

h
i2


E C|α̊, β̊ Var 1α̊,β̊

α̊,β̊

h
i2 



E C|α̊, β̊ P α̊, β̊ 1 − P α̊, β̊

α̊,β̊

h
i2 

E C|α̊, β̊ P α̊, β̊ = E[C]2

α̊,β̊

We conclude that Var(C) ≤ E[C]2 + E[C] .

Note that Theorem 2 implies that the standard deviation
of the number of collisions is about the same as the number
of collisions itself, as bounded in Theorem 1. For Jaccard
index t = J(A, B), the absolute error caused by minimum
hash collisions is then approximately
EC
5
n
= r + p+2q +r .
2p
2
2

6.

q

So long as n < 22 , the second term is bounded by 1/2r .
Then, the absolute error in the Jaccard index estimation
from collisions is bounded by 6/2r , where the constant 6 is
a gross overestimate (empirically, the constant seems closer
to 1). For any desired relative error , we then need only let
r > log

DISCUSSION AND CONCLUSION

We have introduced HyperMinHash, a compressed version
of the MinHash sketch in log log space, and made available a
prototype Python implementation at https://github.com/
yunwilliamyu/hyperminhash. It can be thought of as a
compression scheme for MinHash that reduces the number
of bits per bucket to log log(n) from log(n) by using insights
from HyperLogLog and b-bit MinHash. As with the original
MinHash, it retains variance on the order of k/t, where k is
the number of buckets and t is the Jaccard index between
two sets. However, it also introduces 1/l2 variance, where
l = 2r , because of the increased number of collisions.
For practical parameters of p = 15, q = 6, r = 10, the HyperMinHash sketch will use up 64KiB memory per set, and
allow for estimating Jaccard indices of 0.01 for set cardinalities on the order of 1019 with accuracy around 5%. HyperMinHash is to our knowledge the first practical streaming
summary sketch capable of directly estimating union cardinality, Jaccard index, and intersection cardinality in log log
space, able to be applied to arbitrary Boolean formulas in
conjunctive normal form with error rates bounded by the
final result size.
There remain however many theoretical improvements to
be made, especially in removing the requirement of a random
oracle. Notably, the KNW sketch [15] sketch improves HyperLogLog to using constant size buckets and a double logarithmic offset, while also using limited randomness. Similarly, Feigenblat, et al. introduce d-k-min-wise hash functions to reduce the amount of necessary randomness for a
bottom-k MinHash sketch [11]. We envision that their techniques can be extended to HyperMinHash to further reduce
space complexity, though possibly at the cost of practical
implementation. Indeed, we believe that HyperMinHash as
presented in this manuscript will already be of great practical benefit for Boolean queries on large databases.

= E[X1 ]E[X2 ] Var(Y )

α̊,β̊

EXPERIMENTAL VALIDATION

ACKNOWLEDGMENTS

This study was supported by National Institutes of
Health (NIH) Big Data to Knowledge (BD2K) awards
U54HG007963 from the National Human Genome Research
Institute (NHGRI) and U01CA198934 from the National
Cancer Institute (NCI). The funders had no role in study
design, data collection and analysis, decision to publish, or
preparation of the manuscript. We thank Daphne Ippolito
and Adam Sealfon for useful comments and advice, and Seif
Lotfy for finding a minor bug in our pseudocode. We also
are indebted to all of our reviewers, who kindly but firmly
pointed out missing references and hidden assumptions in
a previous draft of this manuscript.

6
.
t

Of course, for relative error , this then implies that HyperMinHash needs O(log log n + log(1/t)) bits per bucket.
Additionally, note that −2 buckets are needed to control
the error, completing our
proof that HyperMinHash requires
1
bits of space.
O −2 log log n + log t
8

7.

REFERENCES

[11] G. Feigenblat, E. Porat, and A. Shiftan. dk-min-wise
independent family of hash functions. Journal of
Computer and System Sciences, 84:171–184, 2017.
[12] P. Flajolet. Counting by coin tossings. In Advances in
Computer Science-ASIAN 2004. Higher-Level
Decision Making, pages 1–12. Springer, 2004.
[13] P. Flajolet, É. Fusy, O. Gandouet, and F. Meunier.
Hyperloglog: the analysis of a near-optimal cardinality
estimation algorithm. In AofA: Analysis of
Algorithms, pages 137–156. Discrete Mathematics and
Theoretical Computer Science, 2007.
[14] P. Jaccard. Lois de distribution florale dans la zone
alpine. Bull Soc Vaudoise Sci Nat, 38:69–130, 1902.
[15] D. M. Kane, J. Nelson, and D. P. Woodruff. An
optimal algorithm for the distinct elements problem.
In Proceedings of the twenty-ninth ACM
SIGMOD-SIGACT-SIGART symposium on Principles
of database systems, pages 41–52. ACM, 2010.
[16] P. Li and C. König. b-bit minwise hashing. In
Proceedings of the 19th international conference on
World wide web, pages 671–680. ACM, 2010.
[17] P. Li, A. Owen, and C.-H. Zhang. One permutation
hashing. In Advances in Neural Information
Processing Systems, pages 3113–3121, 2012.
[18] R. Pagh, M. Stöckel, and D. P. Woodruff. Is min-wise
hashing optimal for summarizing set intersection? In
Proceedings of the 33rd ACM
SIGMOD-SIGACT-SIGART symposium on Principles
of database systems, pages 109–120. ACM, 2014.
[19] M. Thorup. Bottom-k and priority sampling, set
similarity and subset sums with minimal
independence. In Proceedings of the forty-fifth annual
ACM symposium on Theory of computing, pages
371–380. ACM, 2013.

[1] Y. Bachrach and E. Porat. Fast pseudo-random
fingerprints. arXiv preprint arXiv:1009.5791, 2010.
[2] Y. Bachrach and E. Porat. Fingerprints for highly
similar streams. Information and Computation,
244:113–121, 2015.
[3] Z. Bar-Yossef, T. Jayram, R. Kumar, D. Sivakumar,
and L. Trevisan. Counting distinct elements in a data
stream. In International Workshop on Randomization
and Approximation Techniques in Computer Science,
pages 1–10. Springer, 2002.
[4] A. Z. Broder. On the resemblance and containment of
documents. In Compression and Complexity of
Sequences 1997. Proceedings, pages 21–29. IEEE, 1997.
[5] E. Cohen. Min-hash sketches., 2016.
[6] E. Cohen. Hyperloglog hyperextended: Sketches for
concave sublinear frequency statistics. In Proceedings
of the 23rd ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining, pages
105–114. ACM, 2017.
[7] M. Durand and P. Flajolet. Loglog counting of large
cardinalities. In European Symposium on Algorithms,
pages 605–617. Springer, 2003.
[8] O. Ertl. New cardinality estimation algorithms for
hyperloglog sketches. arXiv preprint
arXiv:1702.01284, 2017.
[9] O. Ertl. New cardinality estimation methods for
hyperloglog sketches. arXiv preprint
arXiv:1706.07290, 2017.
[10] G. Feigenblat, E. Porat, and A. Shiftan. Exponential
time improvement for min-wise based algorithms. In
Proceedings of the twenty-second annual ACM-SIAM
symposium on Discrete Algorithms, pages 57–66.
SIAM, 2011.

9

APPENDIX
A.

Algorithm 3 Estimate Cardinality. Note that the left
parts of the buckets can be passed directly into a HyperLogLog estimator. We can also use other k-minimum value
count-distinct cardinality estimators, which we empirically
found useful for large cardinalities.
function EstimateCardinality(S, p, q, r)
Initialize |S| integer registers b1 = b2 = · · · = b|S| = 0.
for i ∈ {1, . . . , |S|} do
bi ← Si [0]
end for
R ← HyperLogLogCardinalityEstimator({bi }, q)
if R < 1024|S| then
return R
else
Initialize |S| real registers r1 , . . . , r|S| .
for i ∈ {1, . . . , |S|}
 do


HYPERMINHASH IN PRACTICE

Here, we present full algorithms to match a naive implementation of HyperMinHash as described in the previous Theory section. A Python implementation by the authors of this paper is available at https://github.com/
yunwilliamyu/hyperminhash. Additionally, a Go implementation based on this pseudocode was kindly provided by
Seif Lotfy at https://github.com/axiomhq/hyperminhash.
Algorithm 1 HyperMinHash sketch.
1: Let h1 , h2 , h3 : D → [0, 1] ≡ {0, 1}∞ be three independent hash functions hashing data from domain D to the
binary domain. (In practice, we generally use a single
Hash function, e.g. SHA-1, and use different sets of bits
for each of the three hashes).
2: Let ρ(s), for s ∈ {0, 1}∞ be the position of the left-most
1-bit (ρ(0001 · · · ) = 4).
3: Let σ(s, n) for s ∈ {0, 1}∞ be the left-most n bits of s
(σ(01011 · · · , 5) = 01011).
4: function HyperMinHash(A, p, q, r)
5:
Let ĥ1 (x) = σ(h1 (x), p).
6:
Let ĥ2 (x) = min(ρ(h1 (x)), 2q ).
7:
Let ĥ3 (x) = σ(h3 (x), r).
8:
Initialize 2p tuples B1 = B2 = · · · = B2p = (0, 0).
9:
for a ∈ A do
10:
if Bh1 (a) [0] < ĥ2 (a) then
11:
Bĥ1 (a) ← (ĥ2 (a), ĥ3 (a))
12:
else
13:
if Bĥ1 (a) [0] = ĥ2 (a) and Bĥ1 (a) [1] > ĥ3 (a)
then
14:
Bĥ1 (a) ← (ĥ2 (a), ĥ3 (a))
15:
end if
16:
end if
17:
end for
18:
return B1 , . . . , B2p as B
19: end function

ri ← 2−Si [0] · 1 +
end
Pfor
if
ri = 0 then
return ∞
else
P
return |S|2 / ri
end if
end if
end function

Si [1]
2r

Algorithm 4 Compute Jaccard Index. Note that the correction factor EC is generally not needed, except for really
small Jaccard index. Additionally, for most practical purposes, it is safe to substitute ApproxExpectedCollisions
for ExpectedCollisions.
function JaccardIndex(S, T, p, q, r)
assert |S| = |T |
C ← 0, N ← 0
for i ∈ {1, . . . , |S|} do
if Si = Ti and Si 6= (0, 0) then
C ←C +1
end if
if Si 6= (0, 0) or Ti 6= (0, 0) then
N ←N +1
end if
end for
n ← EstimateCardinality(S, q)
m ← EstimateCardinality(T, q)
EC ← [Approx]ExpectedCollisions(n, m, p, q, r)
return (C − EC)/N
end function

Algorithm 2 HyperMinHash Union
function Union(S, T )
assert |S| = |T |
for i ∈ {1, . . . , |S|} do
Initialize |S| tuples B1 = B2 = · · · = B|S| = (0, 0).
if Si [0] > Ti [0] then
Bi ← Si
else if Si [0] < Ti [0] then
Bi ← Ti
else if Si [0] = Ti [0] then
if Si [[1] < Ti [1] then
Bi ← Si
else
Bi ← Ti
end if
end if
end for
return B1 , . . . , B2p as B
end function

10

Algorithm 5 Expected collisions. Note that because of
floating point error, BigInts must be used for large n and
m.
function ExpectedCollisions(n, m, p, q, r)
x←0
for i ∈ {1, . . . , 2q } do
for j ∈ {1, . . . , 2r } do
if i 6= 2q then
r
+j+1
2r +j
, b2 ← 22p+r+i
b1 ← 2p+r+i
else
j
j+1
b1 ← 2p+r+i−1
, b2 ← 2p+r+i−1
end if
P rx ← (1 − b2 )n − (1 − b1 )n
P ry ← (1 − b2 )m − (1 − b1 )m
x ← x + P rx P ry
end for
end for
return x · 2p
end function

Jaccard index computation while using only one comparison per bucket instead of two.
2. Use the max instead of min of the subbuckets. This
allows us take the union of two sketches while using
only one comparison per bucket.
These recommendations should be self-explanatory, and are
simply minor engineering optimizations, which we do not
use in our prototyping, as they do not affect accuracy.
However, while we can exactly compute the number of expected collisions through Lemma 4, this computation is slow
and often results in floating point errors unless BigInts are
used because Algorithm 5 is exponential in r. In practice,
two ready solutions present themselves:
1. We can ignore the bias and simply add it to the error.
As the bias and standard deviation of the error are the
same order of magnitude, this only doubles the absolute error in the estimation of Jaccard index. For large
Jaccard indexes, this does not matter.
2. We also present a fast, numerically stable, algorithm to
approximate the expected number of collisions (Algorithm 6).

Algorithm 6 Fast numerically stable approximation to
Algorithm 5. Generally underestimates collisions.
function ApproxExpectedCollisions(n, m, p, q, r)
if n < m then
SWAP(x, y)
end if q
if n > 22 +r then
return ERROR: cardinality too large for approximation.
else if n > 2p+5 then
4n/m
φ ← (1+n/m)
2
return
0.169919487159739093975315012348 ·
2p−r φ
else
return ExpectedCollisions(n, m, p, q, 0) ·2−r
end if
return x · 2p
end function

A.1

We can however approximate the number of expected collisions using the following procedure, which is empirically
asymptotically correct (Algorithm 6):
1. For n < 2p+5 , we approximate by taking the number
of expected HyperLogLog collisions and dividing it by
2r . In each HyperLogLog box, we are interested in collisions along 2r boxes along the diagonal 4. For this
approximation, we simply assume that the joint probability density function is almost uniform within the
box; this is not completely accurate, but pretty close
in practice.
q

2. For 2p+5 < n < 22 +p , we noted empirically that the
expected number of collisions approached 0.1699 · 2p−r
for n = m as n → ∞. Furthermore, the number
of collisions is dependent on n and m by a factor of
4nm
from 7, which for n, m  1 can be ap(n+m)(n+m−1)
4n/m
proximated by (1+(n/m)
2 . This approximation is primarily needed because of floating point errors when
n → ∞.

Implementation optimizations

We recommend several optimizations for practical implementations of HyperMinHash. First, it is mathematically
equivalent to:

q

3. Unfortunately, around n > 22 +p , the number of collisions starts increasing and these approximations fail.
However, note that for reasonable values of q = 6, p =
15, this problem only appears when n > 289 ≈ 1026 .

1. Pack the hashed tuple into a single word; this enables

11

