Exact Weighted Minwise Hashing in Constant Time

Anshumali Shrivastava
Department of Computer Science, Rice University, Houston, TX, USA

arXiv:1602.08393v1 [] 26 Feb 2016

Abstract
Weighted minwise hashing (WMH) is one
of the fundamental subroutine, required by
many celebrated approximation algorithms,
commonly adopted in industrial practice for
large scale-search and learning. The resource bottleneck of the algorithms is the
computation of multiple (typically a few
hundreds to thousands) independent hashes
of the data. The fastest hashing algorithm
is by Ioffe (Ioffe, 2010), which requires one
pass over the entire data vector, O(d) (d is the
number of non-zeros), for computing one
hash. However, the requirement of multiple hashes demands hundreds or thousands
passes over the data. This is very costly for
modern massive dataset.
In this work, we break this expensive barrier and show an expected constant amortized time algorithm which computes k independent and unbiased WMH in time O(k)
instead of O(dk) required by Ioffe’s method.
Moreover, our proposal only needs a few
bits (5 - 9 bits) of storage per hash value compared to around 64 bits required by the stateof-art-methodologies. Experimental evaluations, on real datasets, show that for
computing 500 WMH, our proposal can be
60000x faster than the Ioffe’s method without losing any accuracy. Our method is also
around 100x faster than approximate heuristics capitalizing on the efficient “densified”
one permutation hashing schemes (Shrivastava & Li, 2014a). Given the simplicity of our
approach and its significant advantages, we
hope that it will replace existing implementations in practice.

1. Introduction and Motivation
(Weighted) Minwise hashing (or Minwise Sampling)
(Broder, 1997; Broder et al., 1997; Manasse et al.,

ANSHUMALI @ RICE . EDU

2010) is the most popular and successful randomized hashing technique (Shrivastava & Li, 2014b),
commonly deployed in commercial big-data systems (Henzinge, 2004; Henzinger, 2006) for large scale
search and learning. Minwise hashing was originally developed for fast similarity estimation. However, quickly it was found that the same sampling (or
hashing) scheme made several applications over the
web, such as, near-duplicate detection (Broder, 1998;
Henzinger, 2006), all-pairs similarity (Bayardo et al.,
2007), record linkage (Koudas et al., 2006), temporal correlations (Chien & Immorlica, 2005), etc., efficient by drastically reducing their computational and
memory requirements.
The idea underlying Minwise hashing is also the key
breakthrough that led to the theory of Locality Sensitive Hashing (LSH) (Indyk & Motwani, 1998). In
particular, minwise sampling is a known LSH for the
Jaccard similarity (Rajaraman & Ullman). Given two
positive vectors x, y ∈ RD , x, y > 0, the (generalized)
Jaccard similarity is defined as
PD
min{xi , yi }
.
(1)
J(x, y) = PDi=1
i=1 max{xi , yi }
J(x, y) is a frequently used measure for comparing
web-documents (Broder, 1997), histograms (specially
images (Ioffe, 2010)), gene sequences (Rasheed &
Rangwala), etc. Recently, it was shown to be a
very effective kernel for large-scale non-linear learning (Li, 2015). Furthermore, it was found that WMH
leads to the best-known LSH for L1 distance (Ioffe,
2010), commonly used in computer vision, improving
over (Datar et al., 2004).
Weighted Minwise Hashing (WMH) (or Minwise
Sampling) generates randomized hash (or fingerprint) h(x), of the given data vector x ≥ 0, such that
for any pair of vectors x and y, the probability of hash
collision (or agreement of hash values) is given by,
P
min{xi , yi }
= J(x, y).
(2)
Pr(h(x) = h(y)) = P
max{xi , yi }
A notable special case is when x and y are binary (or

Exact Weighted Minwise Hashing in Constant Time

sets), i.e. xi , yi ∈ {0, 1}D . For this
case, the similarity
P
min{xi ,yi }
measure boils down to J(x, y) = P max{x
= |x∩y|
|x∪y| .
i ,yi }
Being able to generate a randomized signature, h(x),
satisfying Equation 2 is the key breakthrough behind
some of the best-known approximations algorithms
for metric labelling (Kleinberg & Tardos, 1999), metric
embedding (Charikar, 2002), mechanism design and
differential privacy (Dwork & Roth).
A typical requirement for algorithms relying on minwise hashing is to generate, some large enough, k
independent Minwise hashes (or fingerprints) of the
data vector x, i.e. compute hi (x) i ∈ {1, 2, ..., k} repeatedly with independent randomization. These independent hashes can then be used for a variety of data
mining tasks such as cheap similarity estimation, indexing for sublinear-search, kernel features for large
scale learning, etc. The bottleneck step in all these
applications is the costly computation of the multiple hashes, requiring multiple passes over the data.
The number of required hashes typically ranges from
few hundreds to several thousand (Shrivastava & Li,
2014a;c). For example, the number of hashes required
by the famous LSH algorithm is O(nρ ) which grows
with the size of the data. (Li, 2015) showed the necessity of around 4000 hashes per data vector in largescale learning with J(x, y) as kernel, making hash generation the most costly step.
Owing to the significance of WMH and its impact in
practice, there is a series of work over the last decade
trying to reduce the costly computation cost associated with hash generation (Haeupler et al., 2014).
The first groundbreaking work on Minwise hashing (Broder, 1997) computed hashes h(x) only for unweighted sets x (or binary vectors), i.e. when the
vector components xi s can only take values 0 and 1.
Later it was realized that vectors with positive integer weights, which are equivalent to weighted sets,
can be reduced to unweighted set by replicating elements in proportion to their weights (Gollapudi &
Panigrahy, 2006; Haeupler et al., 2014). This scheme
was very expensive due to blowup in the number of
elements caused by replications. Also, it cannot handle real weights. In (Haeupler et al., 2014), the authors
showed few approximate solutions based on ideas
developed in (Gollapudi & Panigrahy, 2006; Kleinberg & Tardos, 1999) to reduce these replications.
Later (Manasse et al., 2010), introduced the concept of
consistent weighted sampling (CWS), which focuses
on sampling directly from some well-tailored distribution to avoid any replication. This method, unlike
previous ones, could handle real weights exactly. Go-

ing a step further, Ioffe (Ioffe, 2010) was able to compute the exact distribution of minwise sampling leading to a scheme with worst case O(d), where d is the
number of non-zeros. This is the fastest known exact
weighted minwise sampling scheme so far. Since this
will be our main baseline, we review it in Section 2.
O(dk) for computing k independent hashes is very
expensive for modern massive datasets, especially
when k with ranges up to thousands. Recently, there
was a big success for the binary case, where using
the novel idea of “Densification” (Shrivastava & Li,
2014a;c) the computation time for unweighted minwise was brought down to O(d + k). This resulted
into over 100-1000 fold improvement. However, this
speedup was limited only to binary vectors. Moreover, the samples were not completely independent.
Capitalizing on recent advances for fast unweighted
minwise hashing, (Haeupler et al., 2014) exploited the
old idea of replication to convert weighted sets into
unweighted sets. To deal with non-integer weights,
the method samples the coordinates with probabilities proportional to leftover weights. The overall process converts the weighted minwise sampling to an
unweighted problem, however, at a cost of incurring
some bias (see Algorithm 2). This scheme is faster
than Ioffe’s scheme but, unlike other prior works on
CWS, it is not exact and leads to biased and correlated samples. Moreover, it requires strong independence (Indyk, 2001) leading to poor estimation.
All these lines of work lead to a natural question:
does there exist an unbiased and independent WMH
scheme with same property as Ioffe’s hashes but significantly faster than all existing methodologies? We
answer this question positively.
1.1. Our Contributions:
1. We provide an unbiased weighted minwise hashing scheme, where each sampling scheme takes
constant time in expectation. This improves
upon the best-known scheme in the literature by
Ioffe (Ioffe, 2010) which takes O(d), where d is the
number of non-zeros in the data vector.
2. Our hashing scheme requires much fewer bits
usually (5-9) bits instead of 64 bits (or higher) required by existing schemes, leading to around 8x
savings in space.
3. We derive our scheme from elementary first principles. Our scheme is simple and it only requires access to simple uniform random number
generator, instead of costly sampling needed by
other methods. The hashing procedure is differ-

Exact Weighted Minwise Hashing in Constant Time

ent from traditional schemes and could be of independent interest in itself.
4. Experimental evaluations on real image histograms show more than 60000x speedup over
the best known exact scheme and around 100x
times faster than biased approximate schemes
based on the recent idea of fast minwise hashing.
5. Weighted Minwise sampling is a fundamental
subroutine in many celebrated approximation algorithms. Some of the immediate consequences
of our proposal are as follows:
• We obtain an algorithmic improvement,
over the query time of LSH based algorithm, for L1 distance and Jaccard Similarity search. In particular, we reduce the
worst-case query time of (K, L) parameterized LSH algorithm (Andoni & Indyk, 2006)
from O(dKL) to mere O(KL + dL).
• We reduce the kernel feature (Rahimi &
Recht, 2007) computation time with minmax kernels (Li, 2015).
• We reduce the sketching time for fast estimation of a variety of measures, including L1
and earth mover distance (Kleinberg & Tardos, 1999; Charikar, 2002).

2. Review: Ioffe’s Algorithm and Fast
Unweighted Minwise Hashing
Algorithm 1 Ioffe’s CWS (Ioffe, 2010)
input Vector x, random seed[][]
for i = 1 to k do
for Iterate over x j s.t x j > 0 do
randomseed = seed[i][ j];
Sample ri, j , ci, j ∼ Gamma(2, 1).
Sample
 βi, j ∼ Uni
 f orm(0, 1)
tj =

log x j
ri, j

+ βi, j

y j = exp(ri, j (t j − βi, j ))
z j = y j ∗ exp(ri, j )
a j = ci, j /z j
end for
k∗ = arg min j a j
HashPairs[i] = (k∗ , tk∗ )
end for
RETURN HashPairs[]
We briefly review the state-of-the-art methodologies
for Weighted Minwise Hashing (WMH). Since WMH
is only defined for weighted sets, our vectors under
consideration will always be positive, i.e. every xi ≥

0. D will denote the dimensionality of the data, and
we will use d to denote the number (or the average)
of non-zeros of the vector(s) under consideration.
The fastest known scheme for exact weighted minwise hashing is based on an elegant derivation of
the exact sampling process for “Consistent Weighted
Sampling” (CWS) due to Ioffe (Ioffe, 2010). This made
computation of a single weighted minwise hash h(x)
possible in O(d). Although this is still slow for modern massive datasets, it is a good improvement over
the prior works which rely on expensive rejection
based sampling to sample from the CWS distribution (Manasse et al., 2010). Ioffe’s overall algorithm,
samples from some smartly tailored distribution to
achieve the required Equation 2. The overall procedure is summarized in Algorithm 1.
O(d) for a single hash computation is quite expensive.
Even the unweighted case of minwise hashing had
complexity O(d) per hashes, until recently. (Shrivastava & Li, 2014a;c) showed a new one permutation
based scheme for generating k near-independent unweighted minwise hashes in O(d + k) breaking the old
O(dk) barrier. However, this improvement does not
directly extend to the weighted case.
It was known that with some bias, weighted minwise sampling can be reduced to an unweighted minwise sampling using the idea of replicating weights
in proportion to their probabilities (Gollapudi & Panigrahy, 2006; Kleinberg & Tardos, 1999). Algorithm 2
describes such a procedure. A reasonable idea is then
to use the fast unweighted hashing scheme, on the
top of this biased approximation. The inside for-loop
in Algorithm 2 blows up the number of non-zeros in
the returned unweighted set. This makes the process
slower and dependent on the magnitude of weights.
Moreover, unweighted sampling requires very costly
random permutations for good accuracy (Pătraşcu &
Thorup, 2010), which is further biased due to bias incurred during approximation.
Both the Ioffe’s scheme and the biased un-weighted
approximation scheme generate big hash values requiring 32-bits or higher storage per hash value. For
reducing this to a manageable size of say 4-8 bits, a
commonly adopted practical methodology is to randomly rehash it to smaller space at the cost of loss
in accuracy (Li & König, 2011). It turns out that our
hashing scheme only generates 5-9 bits values, h(x),
satisfying Equation 2, without losing any accuracy.
Next, we present a simple hashing procedure for
weighted minwise hashing, which is unbiased and
runs in expected constant time. We will later demon-

Exact Weighted Minwise Hashing in Constant Time

strate that it can be around 60000x faster than Ioffe’s
scheme and around 100 times faster, in practice, than
the fast un-weighted approximation.

x
𝒙𝟏
𝑴𝟎 = 𝟎

Algorithm 2 Reduce to Unweighted (Haeupler et al.,
2014)
input Vector x,
y

S =φ
for Iterate over x j s.t x j > 0 do
f loorx j = bx j c
for i = 1 to f loorx j do
S = S ∪ (i, j)
end for
r = Uni f orm(0, 1)
if r ≤ x j − f loorx j then
S = S ∪ ( f loorx j + 1, j)
end if
end for
RETURN S (unweighted set)

We will denote the ith component of vector x ∈ RD by
xi . Let mi be the upper bound on the value of component xi in the given dataset. We can always assume
the mi to be an integer, otherwise we take the ceiling
dmi e as our upper bound. Define

k=1

mi = M D = M

𝒚𝟒

𝒚𝟑 = 𝟎

𝑴𝟏

𝑴𝟐

𝑴𝟑

𝑴𝟒 = 𝑴

(3)

Initialise Hashes[] to all 0s.
for i = 1 to k do
randomseed = seed[i];
while true do
r = M × Uni f orm(0, 1);
if ISGREEN(r), (check if r ∈ xred then
break;
end if
randomseed = dr ∗ 1000000e ;
Hashes[i] + +;
end while
end for
RETURN Hashes
Our sampling procedure simply draws an independent random real number between [0, M], if the random number lies in the red region we repeat and resample. We stop the process as soon as the generated
random number lies in the green region. Our hash
value for a given data vector, h(x), is simply the number of steps taken before we stop. We summarize the
procedure in Algorithm 3. More formally,

k=1

If the data is normalized, then mi = 1 and M = D.
Given a vector x, we first create a red-green map associated with it, as shown in Figure 3.1. For this, we first
take an interval [0, M] and divide it into D disjoint intervals, with ith interval being [Mi−1 , Mi ] which is of
PD
the size mi . Note that i=1
mi = M, so we can always
do that. We then create two regions, red and green.
For the ith interval [Mi−1 , Mi ], we mark the subinterval
[Mi−1 , Mi−1 +xi ] as green and the rest [Mi−1 +xi , Mi ] with
red, as shown in Figure 3.1. If xi = 0 for some i, then
the whole ith interval [Mi−1 , Mi ] is marked as red.
Formally, for a given vector x, define the green xgreen
and the red xred regions as follows
D
xgreen = ∪i=1
[Mi , Mi +xi ];

𝒚𝟐

𝑴𝟒 = 𝑴

𝑴𝟑 𝒙 𝟒

𝑴𝟐

Algorithm 3 Weighted MinHash
input Vector x, Mi ’s, k, random seed[].

3.1. Procedure

D
X

𝒙𝟑

Figure 1. Illustration of Red-Green Map of 4 dimensional
vectors x and y.

We first describe our procedure in details. We will
later talk about the correctness of the scheme, and we
will show that our proposed scheme can be implemented in expected constant time.

mi = Mi . and

𝒚𝟏
𝑴𝟎 = 𝟎

3. Our Proposal: New Hashing Scheme

i
X

𝒙𝟐
𝑴𝟏

D
xred = ∪i=1
[Mi +xi , Mi+1 ]; (4)

Definition 1 Define {ri : i = 1, 2, 3....} as a sequence of
i.i.d uniformly generated random number between [0, M].
Then we define the hash of x, h(x) as
h(x) = arg min ri , s.t. ri ∈ xgreen
i

(5)

We want our hashing scheme to be consistent (Ioffe,
2010) across different data points to guarantee Equation 2. This requires ensuring the consistency of
the random numbers in hashes (Ioffe, 2010). We
can achieve the required consistency, either by pregenerating sequence of random numbers and storing
them analogous to other hashing schemes. However,
there is an easy way to generate a sequence of random numbers by ensuring the consistency of the random seed. This does not require any storage, except

Exact Weighted Minwise Hashing in Constant Time

the starting seed. Our Algorithm 3 uses this criterion,
to ensure that the sequence of random numbers is the
same, we start with a fixed random seed for generating random numbers. If the generated random number lies in the red region, then before re-sampling, we
reset the seed of our random number generator as a
function of discarded random number. In the algorithm, we used d100000 ∗ re, where de is the ceiling operation, as a convenient way to ensure the consistency
of sequence, without any memory overhead. This
also works nicely in practice. Since we are sampling
real numbers, the probability of any repetition (or cycle) is zero. For generating k independent hashes we
just use different random seeds which are kept fixed
for the entire dataset.
3.2. Proof of Correctness
We show that the simple scheme given in Algorithms 3 actually does possess the required property,
i.e. for any pair of points x and y Equation 2 holds.
Unlike the previous works on this line (Manasse et al.,
2010; Ioffe, 2010) which requires computing the exact
distribution of associated quantities, the proof of our
proposed scheme is elementary and can be derived
from first principles. This is not surprising given the
simplicity of our procedure.
Theorem 1 For any two vectors x and y, we have
PD


min{xi , yi }
Pr h(x) = h(y) = J(x, y) = PDi=1
i=1 max{xi , yi }

(6)

(7)

For any pair of points x and y, consider the following
three events: 1) h(x) = h(y) = j, 2) h(x) > h(y) = j and
3) j = h(x) < h(y). Observe that,
h(x) = h(y) = j if and only if r j ∈ xgreen ∩ ygreen

(8)

h(x) > h(y) = j if and only if r j ∈ ygreen − xgreen

(9)

h(y) > h(x) = j if and only if r j ∈ xgreen − ygreen

(10)

Since r j is uniformly chosen, we have,


Pr h(x) = h(y)
|xgreen ∩ ygreen |
|(xgreen ∩ ygreen ) ∪ (xgreen − ygreen ) ∪ (ygreen − xgreen )|
|xgreen ∩ ygreen |
=
(11)
|xgreen ∪ ygreen |
=

D
D
|xgreen ∩ ygreen | = | ∪i=1
[Mi , Mi + xi ] ∩ ∪i=1
[Mi , Mi + yi ]|
D
X

D
= | ∪i=1
[Mi , Mi + min{xi , yi }]| =

min{xi , yi }

(12)

i=1

and
D
D
|xgreen ∪ ygreen | = | ∪i=1
[Mi , Mi + xi ] ∪ ∪i=1
[Mi , Mi + yi ]|
D
= | ∪i=1
[Mi , Mi + max{xi , yi }]| =

D
X

max{xi , yi },

(13)

i=1

Theorem 1 implies that the sampling process is exact
and we automatically have an unbiased estimator of
J(x, y), using k independently generated WMH, hi (x)s
from Algorithm 3.
k


1 X
ˆ = J(x, y);
Jˆ =
1{hi (x) =hi (y)} ; E( J)
k i=1
ˆ =
Var( J)

J(x, y)(1 − J(x, y))
,
k

(14)
(15)

where 1 is the indicator function.
3.3. Running Time Analysis and Fast
Implementation

Proof: First note that, every number between [0, M]
is random and equally likely in a random sampling.
Therefore, for a given point x, at the time we stop
we sample uniformly from the green region xgreen =
D
∪i=1
[Mi , Mi + xi ]. Consider the index j defined as,
j = min{h(x), h(y)}

The proof follows from substituting the values of
|xgreen ∩ ygreen | and |xgreen ∪ ygreen | given by:

Define
Size of green region
sx =
=
Size of red region

PD
i=1

M

xi

=

||x||1
,
M

(16)

as the effective sparsity of the vector x. Note that this
is also the probability of Pr(r ∈ xgreen ). Algorithm 3
has a while loop.
We show that the expected times the while loops runs,
which is also the expected value of h(x), is a small constant. Formally,
Theorem 2
1 − sx
1
; Var(h(x)) =
;
sx
s2x

log δ 
Pr h(x) ≥
≤ δ.
log (1 − s x )

E(h(x)) =

(17)
(18)

Proof: Equation 17 follows immediately from the fact
that the number of sampling step taken before the
process stops,which is also h(x) is a geometric random
variable with p = s x . Equation 18 follows from observing that Pr(h(x) > k) = (1 − s x )k ≤ δ which implies
δ
k ≤ loglog
(1−s x ) yielding the required bound.

Exact Weighted Minwise Hashing in Constant Time

Remarks: The time to compute each hash value in expectation is the inverse of effective sparsity 1s . Therefore, for datasets with 1s << d, we can expect our
method to be much faster. For real datasets, such as
image histograms, where minwise sampling is popular(Ioffe, 2010), the value of this sparsity is of the order of 0.02-0.08 (see Section 5.2) leading to s1x ≈ 13−50.
On the other hand, the number of non-zeros is around
half million. Therefore, we can expect significant
speed-up in practice.
As a consequence of Theorem 2 we have:
Corollary 1 The expected amount of bits required to represent h(x) is small, in particular,
E(bits) ≤ − log s x ; E(bits) ≈ log

1 (1 − s x )
;
−
sx
2

(19)

Proof: The proof follows from Jensens Inequality,
E(log x) ≤ log E(x) and second order Taylor series apVar(x)
proximation of E(log x) ≈ log E(x) − 2 log
E(x)2
Remarks: Existing hashing scheme require 64 bits,
which is quite expensive. A popular approach for reducing space uses least significant bits of hashes (Li &
König, 2011; Ioffe, 2010). This tradeoff in space comes
at the cost of accuracy (Li & König, 2011). Our hashing scheme naturally requires only few bits, typically
5-9 (see Section 5.2), eliminating the need for trading
accuracy for manageable space.
We know from Theorem 2 that each hash function
computation requires a constant number of function calls to ISGREEN(r). If we can implement ISGREEN(r) in constant time, i.e O(1), then we can generate generate k independent hashes in total O(d + k)
time instead of O(dk) required by (Ioffe, 2010). Note
that O(d) is the time to read the input vector which
cannot be avoided. Once the data is loaded into the
memory, our procedure is actually O(k) for computing k hashes, for all k ≥ 1.
Before we jump into a constant time implementation,
we would like readers to note that there is a straightforward binary search algorithm for ISGREEN(r) in
log d time. We consider d intervals [Mi , Mi + xi ] for all i,
such that xi , 0. Because of the nature of the problem,
Mi−1 + xi−1 ≤ Mi ∀i. Therefore, these intervals are disjoint and sorted. Therefore, given a random number
D
r, determining if r ∈ ∪i=1
[Mi , Mi + xi ] only needs binary
search over d ranges. Thus, given that we only need
constant number of random sampling in expectation
before we stop, we already have a scheme that generates k independent hashes in total O(d + k log d) time
improving over best known O(dk) required by (Ioffe,
2010) for unbiased sampling.

Algorithm 4 ComputeHashMaps (Once per dataset)
input Mi ’s,
index =0, CompToM[0] =0
for i = 0 to D − 1 do
if i < D − 1 then
CompT oM[i + 1] = Mi + CompT oM[i]
end if
for j = 0 to Mi − 1 do
IntT oComp[index] = i
index++
end for
end for
RETURN CompToM[] and IntToComp[]

We show that with some algorithmic tricks and few
more data structures, we can implement ISGREEN(r)
in constant time O(1). We need two global precomputed hashmaps, IntToComp (Integer to Vector
Component) and CompToM (Vector Component to M
value). IntToComp is a hashmap that maps every integer between [0, M] to the associated components, i.e.,
all integers between [Mi , Mi+1 ] are mapped to i, because it is associated with ith component. CompToM
maps every component of vectors i ∈ {1, 2, 3, ..., D}
to its associated value Mi . The procedure for computing these hashmaps is straightforward and is summarized in Algorithm 4. It should be noted that these
hash-maps computation is a one time pre-processing
operation over the entire dataset having a negligible
cost. Mi ’s can be computed (estimated) while reading
the data.
Algorithm 5 ISGREEN(r)
input r, x, Hashmaps IntToComp[] and CompToM[]
from Algorithm 4.
index = dre
i = IntT oComp[index]
Mi = CompT oM[i]
if r ≤ Mi + xi then
RETURN TRUE
end if
RETURN FALSE
Using these two pre-computed hashmaps, the ISGREEN(r) methodology works as follows: We first
compute the ceiling of r, i.e. dre, then we find the
component i associated with r, i.e., r ∈ [Mi , Mi+1 ],
and the corresponding associated Mi using hashmaps
IntToComp and CompToM. Finally, we return true if
r ≤ xi + Mi otherwise we return false. The main observation is that since we ensure that all Mi ’s are Integers,
for any real number r, if r ∈ [Mi , Mi+1 ] then the same

Exact Weighted Minwise Hashing in Constant Time

holds for dre, i.e., dre ∈ [Mi , Mi+1 ]. Hence we can work
with hashmaps using dre as the key. The overall procedure of ISGREEN(r) is summarized in Algorithm 5.

over existing methods. We also need to validate our
theory that our scheme is unbiased and should be indistinguishable in accuracy with Ioffe’s method.

Note that our overall procedure is much simpler compared to Algorithm 1. We only need to generate random numbers followed by a simple condition check
using two hash lookups. Our analysis shows that
we have to repeat this only for a constant number of
times. Compare this with the scheme of Ioffe where
for every non-zero component of a vector we need to
sample two Gamma variables followed by computing several expensive transformations including exponentials. We next demonstrate the benefits of our
approach in practice.

Baselines: Ioffe’s method is the fastest known exact
method in the literature, so it serves as our natural
baseline. We also compare our method with biased
unweighted approximations (see Algorithm 2) which
capitalizes on recent success in fast unweighted minwise hashing (Shrivastava & Li, 2014a;c), we call it
Fast-WDOPH (for Fast Weighted Densified One Permutation Hashing). Fast-WDOPH needs very long
permutation, which is expensive. For efficiency, we
implemented the permutation using fast 2-universal
hashing which is also what is recommended in practice (Mitzenmacher & Vadhan, 2008).

4. Practical Issues

Datasets: Weighted Minwise sampling is commonly
used for sketching image histograms (Ioffe, 2010). We
chose two popular publicly available vision dataset
Caltech101 (Fei-Fei et al., 2007) and Oxford (Philbin
et al., 2007). We used the standard publicly available
Histogram of Oriented Gradient (HOG) codes (Dalal
& Triggs, 2005), popular in vision task, to convert images into feature vectors. In addition, we also used
random web images (Wang et al., 1999) and computed simple histograms of RGB values. We call
this dataset as Web-Images Hist. The basic statistics of these datasets is summarized in Table 5. These
datasets cover a wide range of variations in terms of
dimensionality, non-zeros and sparsity.

PD
xi
PDi=1
i=1 Mi

deterTheorem 2 shows that the quantity s x =
mines the runtime. If s x is very very small then, although the running time is constant (independent of
d or D), it can still make the algorithm unnecessarily
slow. Note that for the algorithm to work we choose
Mi to be the largest integer greater than the maximum
possible value of co-ordinate i in the given dataset. If
this integer gap is big then we unnecessarily increase
the running time. Ideally, the best running time is obtained when the maximum value, is itself an integer,
or is very close to its ceiling value. If all the values
are integers, scaling up does not matter, as it does not
change s x , but scaling down can make s x worse. IdePD

αx

ally we should scale, such that, α = arg maxα = PDi=1dαmi e
i
i=1
is maximized, where mi is the maximum value of coordinate i in the given dataset.

5. Experiments
Table 1. Basic Statistics of the Datasets Used in the Paper

Data
Web-Images
Hist
Caltech101
Oxford

non-zeros (d)

Dim (D)

737

768

95029
401879

485640
580644

Sparsity
(s)
0.081
0.024
0.086

We have proposed a new Weighted Minwise Hashing scheme which is significantly faster in theory than
existing methodologies. In this section, we would
like to assess its impact in practice. We compare
the proposed scheme with the existing state-of-artmethodologies on estimation accuracy, running time
and space. In particular, we will demonstrate that
in real high-dimensional settings, our proposal provides significant speedup and requires less memory

Table 2. Time taken in milliseconds (ms) to compute 500
hashes by different schemes. Our proposed scheme is significantly faster.

Method

Prop

Ioffe

Web-Images Hist
Caltech101
Oxford

10ms
57ms
11ms

986ms
87105ms
746120ms

FastWDOPH
57ms
268ms
959ms

5.1. Comparing Estimation Accuracy
Table 3. The range of the observed hash values, using the
proposed scheme, along with the maximum bits needed per
hash value. The mean hash values agrees with Theorem 2

Mean Values
Hash Range
Bits Needed

WebImages
Hist
11.94
[1,107]
7

Caltech101 Oxford

52.88
[1,487]
9

9.13
[1,69]
7

In this section, we perform a sanity check experiment
and compare the estimation accuracy with WMH. For
this task we take 9 pairs of vectors from our datasets
with varying level of similarities. For each of the pair

Exact Weighted Minwise Hashing in Constant Time

Sim=0.8

0.05

0.15
Sim=0.72

0.1
0.05

0

0.15
0.1
0.05

0
10

20

30

40

50

0
10

Number of Hashes

20

30

40

50

0.1

0

0.2

Sim=0.44
0.1

0
10

20

30

40

Number of Hashes

50

20

30

40

10

20

30

40

Number of Hashes

50

20

30

40

50

Number of Hashes
0.4

Proposed
Fast-WDOPH
Ioffe

0.3
Sim=0.35

0.2
0.1
0

10

Sim=0.61
0.1

50

0.4
Proposed
Fast-WDOPH
Ioffe

Average Error

Average Error

0.2

Proposed
Fast-WDOPH
Ioffe

0.2

Number of Hashes

0.3
Sim=0.56

Proposed
Fast-WDOPH
Ioffe

0
10

Number of Hashes

0.3

Average Error

0.2

0.3
Proposed
Fast-WDOPH
Ioffe

Sim=0.67

Average Error

0.1

0.2

Average Error

0.15

0.25
Proposed
Fast-WDOPH
Ioffe

Average Error

0.25
Proposed
Fast-WDOPH
Ioffe

Average Error

Average Error

0.2

Proposed
Fast-WDOPH
Ioffe

0.3
Sim=0.27
0.2
0.1
0

10

20

30

40

50

Number of Hashes

10

20

30

40

50

Number of Hashes

Figure 2. Average Errors in Jaccard Similarity Estimation with the Number of Hash Values. Estimates are averaged over
200 repetitions.

(x, y), we generate k weighted minwise hashes hi (x)
and hi (y) for i ∈ {1, 2, .., k}, using the three competing
schemes. We then compute the estimate of the Jaccard
P 
similarity J(x, y) using the formula 1k ki=1 1{hi (x) =

hi (y)} (See Equation 14). We compute the errors in
the estimate as a function of k. To minimize the effect of randomization, we average the errors from 200
random repetitions with different seeds. We plot this
average error with k = {1, 2, ..., 50} in Figure 2 for
different similarity levels.
We can clearly see from the plots that the accuracy
of the proposed scheme is indistinguishable from
Ioffe’s scheme. This is not surprising because both the
schemes are unbiased and have the same theoretical
distribution. This validates Theorem 1
The accuracy of Fast-WDOPH is inferior to that of the
other two unbiased schemes and sometimes its performance is poor. This is because the weighted to unweighted reduction is biased and approximate. The
bias of this reduction depends on the vector pairs under consideration, which can be unpredictable.
5.2. Speed Comparisons
In this section, we demonstrate the actual benefits of
having a constant time and low memory approach
over existing methodologies. For this task, we compute the average time (in milliseconds) taken by the
competing algorithms to compute 500 hashes of a
given data vector for all the three datasets. Our experiments were coded in C# on Intel Xenon CPU with 256
GB RAM. Table 2 summarises the comparison. We
do not include the data loading cost in these numbers
and assume that the data is in the memory for all the

three methodologies.
We can clearly see tremendous speedup over Ioffe’s
scheme. For Web-Images dataset with mere 768 nonzeros, our scheme is 100 times faster than Ioffe’s
scheme and around 5 times faster than Fast-WDOPH
approximation. While on caltech101 and Oxford
datasets, which are high dimensional and dense
datasets, our scheme can be 1500x to 70000x faster
than Ioffe’s scheme, while it is around 5 to 100x times
faster than Fast-WDOPH scheme. Dense datasets like
Caltech101 and Oxford represent more realistic scenarios. These features are taken from real applications (Dalal & Triggs, 2005) and such level of sparsity
and dimensionality are more common in practice.
The results are not surprising because Ioffe’s scheme
is very slow O(dk). Moreover, the constant are inside bigO is also large, because of complex transformations. Therefore, for datasets with high values of
d (non-zeros) this scheme is very slow. Similar phenomena were observed in (Ioffe, 2010), that decreasing the non-zeros by ignoring non-frequent dimensions can be around 150 times faster. However, ignoring dimension looses accuracy.
5.3. Memory Comparisons
Table 3 summarizes the range of the hash values and
the maximum number of bits needed to encode these
hash values without any bias. We can clearly see
that the hash values, even for such high-dimensional
datasets, only require 7-9 bits. This is a huge saving compared to existing hashing schemes which can
require (32-64) bits (Li & König, 2011). Note, Ioffe’s
scheme generates a pair of integers as hashes which

Exact Weighted Minwise Hashing in Constant Time

has significant storage cost. Thus, our method leads
to around 5-6 times savings in space and it eliminates
the need of shrinking hashes to small bits with a loss
in the estimation accuracy. The mean values observed
(Table 3) validate the formula in Theorem 2.

6. Conclusions
We show that the existing popular weighted minwise
hashing scheme can be made simpler, significantly
faster and memory efficient. Our theoretical and empirical results show that these advantages come for
free and the hashes are indistinguishable from the unbiased scheme of Ioffe.
Experiments on real datasets show up to 60000
fold speedup in computing 500 hashes compared to
the state-of-the-art procedure. We believe that our
scheme will replace existing implementations in bigdata systems.

References
Andoni, Alexandr and Indyk, Piotr. Near-optimal
hashing algorithms for approximate nearest neighbor in high dimensions. In FOCS, pp. 459–468,
Berkeley, CA, 2006.
Bayardo, Roberto J., Ma, Yiming, and Srikant, Ramakrishnan. Scaling up all pairs similarity search.
In WWW, pp. 131–140, 2007.
Broder, Andrei Z. On the resemblance and containment of documents. In the Compression and Complexity of Sequences, pp. 21–29, Positano, Italy, 1997.
Broder, Andrei Z. Filtering near-duplicate documents. In FUN, Isola d’Elba, Italy, 1998.
Broder, Andrei Z., Glassman, Steven C., Manasse,
Mark S., and Zweig, Geoffrey. Syntactic clustering
of the web. In WWW, pp. 1157 – 1166, Santa Clara,
CA, 1997.
Charikar, Moses S. Similarity estimation techniques
from rounding algorithms. In STOC, pp. 380–388,
Montreal, Quebec, Canada, 2002.
Chien, Steve and Immorlica, Nicole. Semantic similarity between search engine queries using temporal correlation. In WWW, pp. 2–11, 2005.
Dalal, Navneet and Triggs, Bill. Histograms of oriented gradients for human detection. In Computer
Vision and Pattern Recognition, volume 1, pp. 886–
893. IEEE, 2005.

Datar, Mayur, Immorlica, Nicole, Indyk, Piotr, and
Mirrokn, Vahab S.
Locality-sensitive hashing
scheme based on p-stable distributions. In SCG, pp.
253 – 262, Brooklyn, NY, 2004.
Dwork, Cynthia and Roth, Aaron. The algorithmic
foundations of differential privacy.
Fei-Fei, Li, Fergus, Rob, and Perona, Pietro. Learning
generative visual models from few training examples: An incremental bayesian approach tested on
101 object categories. Computer Vision and Image Understanding, 106(1):59–70, 2007.
Gollapudi, Sreenivas and Panigrahy, Rina. Exploiting
asymmetry in hierarchical topic extraction. In Proceedings of the 15th ACM international conference on
Information and knowledge management, pp. 475–482.
ACM, 2006.
Haeupler, Bernhard, Manasse, Mark, and Talwar,
Kunal. Consistent weighted sampling made fast,
small, and easy. Technical report, arXiv:1410.4266,
2014.
Henzinge, Monika .R. Algorithmic challenges in web
search engines. Internet Mathematics, 1(1):115–123,
2004.
Henzinger, Monika. 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, pp. 284–291. ACM, 2006.
Indyk, Piotr. A small approximately min-wise independent family of hash functions. Journal of Algorithms, 38(1):84–90, 2001.
Indyk, Piotr and Motwani, Rajeev. Approximate nearest neighbors: Towards removing the curse of dimensionality. In STOC, pp. 604–613, Dallas, TX,
1998.
Ioffe, Sergey.
Improved consistent sampling,
weighted minhash and L1 sketching. In ICDM, pp.
246–255, Sydney, AU, 2010.
Kleinberg, Jon and Tardos, Eva. Approximation algorithms for classification problems with pairwise
relationships: Metric labeling and Markov random
fields. In FOCS, pp. 14–23, New York, 1999.
Koudas, Nick, Sarawagi, Sunita, and Srivastava, Divesh. Record linkage: similarity measures and algorithms. In Proceedings of the 2006 ACM SIGMOD
international conference on Management of data, pp.
802–803. ACM, 2006.

Exact Weighted Minwise Hashing in Constant Time

Li, Ping. 0-bit consistent weighted sampling. In KDD,
2015.
Li, Ping and König, Arnd Christian. Theory and applications b-bit minwise hashing. Commun. ACM,
2011.
Manasse, Mark, McSherry, Frank, and Talwar, Kunal.
Consistent weighted sampling. Technical Report
MSR-TR-2010-73, Microsoft Research, 2010.
Mitzenmacher, Michael and Vadhan, Salil. Why simple hash functions work: exploiting the entropy in
a data stream. In Proceedings of the nineteenth annual
ACM-SIAM symposium on Discrete algorithms, pp.
746–755. Society for Industrial and Applied Mathematics, 2008.
Philbin, J., Chum, O., Isard, M., Sivic, J., and Zisserman, A. Object retrieval with large vocabularies
and fast spatial matching. In Proceedings of the IEEE
Conference on Computer Vision and Pattern Recognition, 2007.
Pătraşcu, Mihai and Thorup, Mikkel. On the kindependence required by linear probing and minwise independence. In ICALP, pp. 715–726, 2010.
Rahimi, Ali and Recht, Benjamin. Random features
for large-scale kernel machines. In Advances in
neural information processing systems, pp. 1177–1184,
2007.
Rajaraman, Anand and Ullman, Jeffrey. Mining of
Massive Datasets.
Rasheed, Zeehasham and Rangwala, Huzefa. Mcminh: Metagenome clustering using minwise
based hashing. SIAM.
Shrivastava, Anshumali and Li, Ping. Densifying
one permutation hashing via rotation for fast near
neighbor search. In ICML, Beijing, China, 2014a.
Shrivastava, Anshumali and Li, Ping. {In Defense of
Minhash over Simhash}. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, pp. 886–894, 2014b.
Shrivastava, Anshumali and Li, Ping. Improved densification of one permutation hashing. In UAI, Quebec, CA, 2014c.
Wang, J, Li, Jia, Chan, Desmond, and Wiederhold,
Gio. Semantics-sensitive retrieval for digital picture
libraries. D-Lib Magazine, 5(11), 1999.

