MinHash

MinHash (short for min-wise independent permutations locality-sensitive hashing) is a randomized dimensionality-reduction and set-sketching algorithm in computation and algorithms that compresses arbitrarily large sets into fixed-size integer signatures to estimate their Jaccard similarity coefficient J(A, B) = |A ∩ B| / |A ∪ B|. Invented by Andrei Z. Broder in 1997 at Digital Equipment Corporation's Systems Research Center to detect near-duplicate and mirror pages across millions of documents in the AltaVista web search engine, MinHash was also one of the foundational constructions in the theory of locality-sensitive hashing (LSH).

Given two sets A and B of arbitrary cardinality (such as the sets of 5-word w-shingles in two web documents or canonical 21-base-pair DNA k-mers in two sequenced genomes), computing |A ∩ B| / |A ∪ B| directly requires O(|A| + |B|) time and storage for every pair (A, B). MinHash reduces each set A to a compact signature of k minimum hash integers (h_min,1(A), ..., h_min,k(A)) in a single streaming pass so that the fraction of matching signature coordinates is an unbiased estimator of J(A, B) with standard error ≤ 1 / (2√k)—independent of the original set sizes |A| and |B|. Together with HyperLogLog, the Bloom filter, and the Count–Min sketch, MinHash is a cornerstone of web-scale deduplication, LLM pretraining corpus filtering, collaborative filtering, and comparative genomics (Mash and Sourmash).

Resemblance, w-Shingling, and the Jaccard Index

To compare two text documents or biological sequences as sets, Broder (1997) represented each document D as its set S(D, w) of contiguous w-grams (called w-shingles in information retrieval or k-mers in bioinformatics). For two non-empty subsets A, B ⊆ U drawn from a finite universe U = {0, 1, ..., N − 1}, their Jaccard similarity coefficient (resemblance) J(A, B) and Jaccard distance d_J(A, B) are defined as:

Notice that d_J(A, B) satisfies the triangle inequality on finite sets and forms a true mathematical metric space.

Proof of Broder's Min-Wise Collision Theorem

Let π : U → U be a permutation chosen uniformly at random from the symmetric group S_N of all N! permutations of U (or a hash function h : U → [0, 1] mapping elements to distinct random real numbers). Define the MinHash of set A under π as the minimum permuted value across all members of A:

Theorem (Broder, 1997): Over a uniformly random permutation π ∈ S_N, the probability that A and B share the same minimum permuted element equals their Jaccard similarity:

Proof: Consider the restricted set of elements A ∪ B. Because π is a uniformly random permutation of U, every element z ∈ A ∪ B is equally likely to be mapped to the smallest value min_x∈A∪B π(x) among the |A ∪ B| elements of the union, each with probability 1 / |A ∪ B|. Moreover, since min_x∈A∪B π(x) = min( h_π(A), h_π(B) ), the two minimums h_π(A) and h_π(B) are equal if and only if that unique minimum element z^* = arg min_x∈A∪B π(x) belongs to both A and B—that is, z^* ∈ A ∩ B. Since there are |A ∩ B| such elements out of |A ∪ B| equally likely candidates, Pr[h_π(A) = h_π(B)] = |A ∩ B| / |A ∪ B| = J(A, B).

Three Standard MinHash Signature Constructions

Because a single indicator variable I = 1[h_π(A) = h_π(B)] ∈ {0, 1} is a Bernoulli(J) random variable with variance J(1 − J), estimating J(A, B) to within additive error ε requires combining k = O(1 / ε²) samples via one of three architectures:

1. k-Hash Function MinHash: Choose k independent universal hash functions h₁, h₂, ..., h_k and store the vector M(A) = [h_min,1(A), ..., h_min,k(A)]. The estimator Ĵ(A, B) = (1 / k) ∑_i=1..k 1[h_min,i(A) = h_min,i(B)] has expected value J and standard deviation √( J(1 − J) / k ) ≤ 1 / (2√k). For k = 400 hashes, standard error is ≤ 2.5%, at the cost of O(k |A|) hash evaluations per set.
2. Bottom-k (Single-Hash k-Mins) Sketch: Apply a single hash function h to all elements of A and retain the k smallest hashed values min_k(h(A)) in a bounded max-heap of size k (taking only O(|A| log k) time). To estimate J(A, B), merge the two sorted bottom-k lists of A and B, take the k smallest distinct hashes overall, and count what fraction belong to h(A) ∩ h(B).
3. One-Permutation Hashing (OPH, Li, Owen, & Zhang, 2012) & Densification (Shrivastava, 2017): Partition the output space of a single hash function h into k equal bins (exactly like HyperLogLog bucketing) and record the minimum hash value within each bin in O(|A|) time, using optimal rotational densification to fill any empty bins when |A| < k log k.

Comparing all (N choose 2) = O(N²) MinHash signatures directly across N = 10⁸ documents is still quadratic in N. To achieve sublinear query time via locality-sensitive hashing, the k-element MinHash signature vector is partitioned into b bands of r rows each (k = b · r):

• For each band j ∈ {1, ..., b}, the r integers in band j are concatenated and hashed into a standard hash table bucket. Two documents become candidate duplicates if they collide in at least one of the b bands.
• Because the probability that all r rows in a single band match is J^r, the probability that A and B collide in at least one of the b independent bands follows the sharp S-curve:

with inflection threshold τ ≈ (1 / b)^1/r (for example, k = 100 split into b = 20 bands of r = 5 rows gives threshold τ ≈ (1/20)^1/5 ≈ 0.549: pairs with J = 0.80 are captured with probability 99.96%, while pairs with J = 0.20 collide with probability only 0.64%).

In comparative genomics (Mash, Ondov et al., 2016), bottom-k MinHash sketches (k = 1,000 canonical 21-mers, occupying 8 KB per genome) transform the estimated Jaccard index j = Ĵ(A, B) into the evolutionary Mash distance D (approximating 1 − Average Nucleotide Identity, 1 − ANI) under a Poisson mutation model of k-mer survival probability (1 − D)^k = 2j / (1 + j):

enabling all-pairs clustering of 54,118 NCBI RefSeq genomes in 33 CPU hours instead of years of alignment.

Do we need true random permutations of the universe to implement MinHash?

No. Storing a true random permutation of a 64-bit universe is impossible, and Piotr Indyk (2001) proved that O(log(1/ε))-wise independent hash functions approximate min-wise independent permutations with negligible bias ≤ ε. In practice, simple universal affine hashes h_i(x) = (a_ix + b_i) mod p or 64-bit MurmurHash3 / xxHash with distinct seeds achieve the theoretical 1 / √k standard error.

When should FracMinHash (Containment MinHash) be used instead of standard Bottom-k MinHash?

When comparing a small viral genome (A, 10⁴ k-mers) against a massive host metagenome (B, 10⁹ k-mers), their Jaccard similarity J(A, B) = |A ∩ B| / |A ∪ B| ≤ 10⁻⁵ is nearly zero even if 100% of A is contained inside B, so a fixed-size bottom-k sketch of B misses almost all hashes of A. FracMinHash (used in Sourmash) retains all hashes below a fixed threshold H_max = 2⁶⁴ / s (e.g., scale factor s = 1,000), directly estimating the containment index C(A, B) = |A ∩ B| / |A| without dilution by |B|.

How does Weighted MinHash extend Jaccard similarity to real-valued frequency vectors?

For non-negative real vectors x, y ∈ ℝ_≥0^d, the generalized (weighted) Jaccard similarity is J_W(x, y) = ∑_i min(x_i, y_i) / ∑_i max(x_i, y_i). Sergey Ioffe's Consistent Weighted Sampling (ICWS, 2010) samples Gamma(2, 1) (sum of two exponential distribution draws) and uniform random variables per active coordinate i (x_i > 0) so that the probability of selecting the same coordinate-value pair equals J_W(x, y) in O(nnz(x)) time independent of the magnitude of x_i.

1. Broder, A. Z. (1997). "On the resemblance and containment of documents." Proceedings of the Compression and Complexity of Sequences 1997 (SEQUENCES '97), IEEE, 21–29. https://doi.org/10.1109/SEQUEN.1997.666900
2. Broder, A. Z., Charikar, M., Frieze, A. M., & Mitzenmacher, M. (2000). "Min-wise independent permutations." Journal of Computer and System Sciences, 60(3), 630–659. https://doi.org/10.1006/jcss.1999.1690
3. Ioffe, S. (2010). "Improved consistent sampling, weighted minhash and L1 sketching." 2010 IEEE International Conference on Data Mining (ICDM), 246–255. https://doi.org/10.1109/ICDM.2010.80
4. Li, P., Owen, A. B., & Zhang, C.-H. (2012). "One permutation hashing." Advances in Neural Information Processing Systems (NeurIPS 25), 3113–3121. https://proceedings.neurips.cc/paper/2012/file/baa2be66c6f933fb9efbc4f8bf2a51bf-Paper.pdf
5. Ondov, B. D., Treangen, T. J., Melsted, P., Mallonee, A. B., Bergman, N. H., Koren, S., & Phillippy, A. M. (2016). "Mash: fast genome and metagenome distance estimation using MinHash." Genome Biology, 17(1), 132. https://doi.org/10.1186/s13059-016-0997-x