Research Radar — 2026-11-10

Methodology Review: MinHash: compare large sets by agreeing on what to remember

English · About 10 minutes

Theory and application sections were checked against an author-hosted full text and two publisher full texts. The toy examples and variance calculations are illustrative derivations. Published genomics benchmarks were not independently reproduced. Earlier-version identity metadata was verified, but inaccessible preprint and conference full texts were not compared line by line.

The intuition

Imagine checking whether two enormous bags contain mostly the same kinds of objects. Mailing both bags to a comparison desk is expensive. Mailing a few independently chosen objects from each is also disappointing: even similar bags may send different examples. The useful trick is to coordinate the sampling. Give every possible object the same randomly chosen priority in both bags, then remember whichever object has the highest priority. Shared objects now have a fair opportunity to represent both bags. This is the intuition behind MinHash. [R1]

The word minimum refers to the smallest random rank, not the smallest biological measurement. In a sequencing application, the objects can be distinct k-mers, meaning sequence words of length k. More generally, they could be any well-defined identifiers. A sketch is a small stored summary of a larger set. Before compressing anything, ask what membership means: a set records presence, so repeating an object a thousand times does not give it a thousand votes. Choosing the objects is therefore part of choosing the scientific question. [R1] [R2]

A small worked example

Consider a synthetic universe of four identifiers, a, b, c and d. Set A contains a, b and c; set B contains b, c and d. Their intersection contains two identifiers and their union contains four, so their Jaccard similarity is one-half. These letters could stand for distinct sequence words, but this is an arithmetic example, not a simulated biological dataset. We will use four illustrative priority orders, read from highest priority to lowest. Both sets must use the same order on every trial.

For the order a, b, c, d, A remembers a and B remembers b: no match. For b, d, a, c, both remember b: a match. For c, a, d, b, both remember c: another match. For d, c, b, a, A remembers c and B remembers d: no match. The remembered identifiers are therefore (a, b, c, c) for A and (b, b, c, d) for B. Two of four corresponding positions agree, giving an estimate of one-half. These deliberately displayed orders happen to recover the exact answer; four random trials need not do so.

Why can this work? Look at the first identifier in the union under a random order. If it is b or c, both sets choose it. If it is a or d, their choices differ. Every identifier has the same chance to come first, and exactly half are shared. Notice the role of coordination: drawing a fresh, unrelated order for B would destroy this argument. Repeating one fixed order four times would also add no information. The useful repetition consists of new random orders, each shared between A and B. [R1]

Now imagine a different synthetic comparison. A small reference has 100 distinct words, all present in a mixture containing 10,000 distinct words. Its Jaccard similarity with the mixture is 0.01, yet its containment in that mixture is one. A low resemblance score can therefore coexist with complete inclusion. This example changes no algorithm; it changes the denominator of the question. Decide which question matters before choosing a sketch or interpreting a low score. [R3]

The necessary mathematics

Let A and B be finite, nonempty sets. Write \(\lvert A\rvert\) for the number of distinct elements in A, and use intersection and union in their ordinary set meanings. Define the Jaccard similarity by

Let \(\pi\) assign each element a distinct rank in a uniformly random permutation of a finite universe containing both sets, and let \(h_{\pi}(A)=\min_{x\in A}\pi(x)\), where x ranges over elements of A. The symbol \(\Pr\) denotes probability over the random ordering. The central identity is \(\Pr[h_{\pi}(A)=h_{\pi}(B)]=J(A,B)\). The first-in-the-union argument above explains it without requiring a density model. [R1]

For \(m\) independently drawn permutations, let \(I_i\) equal one when the two minima match on trial \(i\) and zero otherwise. Holding the sets fixed, each indicator has success probability \(J=J(A,B)\). Writing \(\widehat{J}\) for the estimated similarity, averaging the indicators and using independence gives

Expectation and variance here refer only to the randomized sketch. For the toy sets, \(J=1/2\) and \(m=4\) give standard deviation one-quarter. These variance calculations are direct consequences of the cited collision identity, not a claim that four trials provide useful precision. [R1]

Mash uses a related bottom-sketch implementation: keep the smallest \(s\) distinct hash values under one shared hash order, where s is the sketch size, or all values if fewer are available. Merge two sketches to recover the bottom sample of their union, then estimate similarity from the fraction of that sample present in both sets. The union restriction matters; simply dividing every shared sketch entry by \(s\) can be wrong. Those sampled entries are drawn without replacement, so the independent-trial variance formula above is not its exact finite-population variance. For directional containment, the target instead is \(C(A,B)=\lvert A\cap B\rvert/\lvert A\rvert\). Mash Screen tests sampled reference words against the full streamed mixture. [R2] [R3]

Assumptions and failure modes

The exact minimum identity requires an appropriate random ordering. Practical hash functions approximate this ideal, and finite hash values can collide. The primary paper separates min-wise independence from weaker randomness properties; a hash that merely looks well mixed is not automatically an exact implementation of every theorem. Store the hash scheme and seed with the sketch. Also align identifier rules and preprocessing across datasets. Otherwise two identical biological inputs can be encoded as different sets before sampling even begins. [R1] [R2]

Rare overlap is another limitation. In the independent-trial estimator, if \(J=0.01\) and \(m=100\), the probability of observing no matches is \((1-0.01)^{100}\approx0.366\). This is a direct calculation under the stated model: a zero sketch estimate can occur despite nonzero overlap. Increasing the sketch size addresses sampling error, but cannot fix an inappropriate similarity target. Nor does a more precise sketch supply biological replication. Sampling randomness conditional on two observed sets is different from uncertainty about the populations that generated them. [R1]

Sequence representation adds separate failure modes. Short k-mers can match by chance; long ones are more easily disrupted by sequence differences. Read errors and filtering alter which words enter the set. Mash Screen also warns that incomplete coverage and sequence divergence can both lower containment. Thus a match supports shared words, while a missing word alone cannot identify why it is absent. The interpretation needs coverage, contamination and reference-database checks suited to the experiment. [R2] [R3]

Verified applications

Ondov and colleagues used Mash to sketch and cluster 54,118 RefSeq genomes and to compare metagenomic collections. Their paper reports approximately 33 CPU hours for sketching plus all-pairs distances in that historical benchmark. This verifies an application of compact set summaries to large genomic comparisons, not a current hardware guarantee. The additional conversion from word-set similarity to mutation distance relies on an evolutionary model; the MinHash identity alone does not establish sequence identity or evolutionary relatedness. [R2]

The Mash Screen study verified a different use: searching reference genome or proteome sketches against sequencing mixtures. Its reported demonstrations include contaminant screening and identification followed by assembly of a novel polyomavirus from a public metagenome. The distinction is operational as well as mathematical: the mixture is streamed against reference sketches rather than reduced to an equally small bottom sketch. These are published demonstrations inspected in full text; the present review does not independently rerun their analyses or validate clinical detection. [R3]

Possible transfers — speculative

A possible transfer is a preliminary search over large collections of binary gene-detection sets: use sketches to retrieve candidate neighbors, then calculate exact similarity for the shortlisted pairs. This is a proposed experiment, not a validated workflow from these papers. Detection thresholds and assay sensitivity would need careful control because they change membership. Compare the shortlist with exact searches on a manageable subset, and evaluate missed neighbors rather than speed alone. If abundance or direction of change is the scientific signal, a presence-only representation may discard what matters.

Another proposed use is organizing very large annotation collections by overlap in standardized feature identifiers. Start with an explicit choice between resemblance and containment, then test whether conclusions survive alternative identifier mappings. Keep the full original objects available for verification. A sketch can help decide where to spend an expensive comparison, but a downstream scientific claim should be checked against the retained evidence. Neither proposal follows automatically from successful genome sketching.

What to try and what to read next

Try the four-identifier example first. Enumerate all 24 possible orders and check that exactly 12 make the minima agree. Then repeatedly draw a few orders and watch the estimate fluctuate. Finally, add many new identifiers only to B and explain why resemblance drops while containment of A may stay fixed. Read the opening pages of the primary paper for the randomness contract, Mash for bottom sketches, and Mash Screen for the change of target. The practical lesson is to agree on both what to remember and what that memory is meant to estimate. [R1] [R2] [R3]

Reading list

• [R1] Primary reading: Min-Wise Independent Permutations. Broder, Charikar, Frieze and Mitzenmacher (2000). Read the introduction through equation (6), especially pages 632–634. It explains the randomness property behind the sketch; the later combinatorial constructions are optional. The 1998 STOC extended abstract is the same research lineage and is tracked as an alias, not a second reading.

• [R2] Related reading: Mash: fast genome and metagenome distance estimation using MinHash. Ondov, Treangen, Melsted, Mallonee, Bergman, Koren and Phillippy (2016). Read Figure 1 before the genomic benchmarks. Mash keeps several minima under one hash order, which differs from the independent-permutation teaching estimator. Its mutation-distance interpretation adds assumptions beyond set similarity.

• [R3] Related reading: Mash Screen: high-throughput sequence containment estimation for genome discovery. Ondov, Starrett, Sappington, Kostic, Koren, Buck and Phillippy (2019). Read the introduction, Figures 1–2 and the limitations paragraph. This is the practical companion for asking whether a small reference is present inside a much larger mixture, rather than whether two mixtures resemble each other.