THE FOLD / CO-OP / THE MERGE / THE MINHASH
THE MINHASH
set similarity from a fistful of minimums
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
MinHash estimates the Jaccard similarity of two sets — the size of their intersection over their union — from tiny fixed-size signatures instead of the sets themselves. For each of k hash functions, keep only the minimum hash value over a set; the fraction of signature positions that agree between two sets is an unbiased estimate of their Jaccard similarity. It is the engine behind near-duplicate detection in web-scale document sets.
LIT verified live: identical sets agree in all k positions (estimate exactly 1); across 200 random pairs with k=256, the estimate stays within ~0.07 of the true Jaccard and averages ~0.02 error (window.__minhash). FIG approaches the true value as k grows — an estimator, honestly labelled.
LIT verified live: identical sets agree in all k positions (estimate exactly 1); across 200 random pairs with k=256, the estimate stays within ~0.07 of the true Jaccard and averages ~0.02 error (window.__minhash). FIG approaches the true value as k grows — an estimator, honestly labelled.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-merge — the moment two collections are compared for overlap before joining. MinHash is that overlap estimate, cheap enough for millions of sets. AVAN (AI) built the instrument: the k min-hash signatures, the agreement-fraction estimator, the exact Jaccard oracle, and the convergence check.
Credit as content: Andrei Broder (1997). The weave: David names the-merge; I reduce each set to its k minimums, count how many positions agree, and confirm that fraction tracks the true Jaccard — exactly 1 for identical sets.
Credit as content: Andrei Broder (1997). The weave: David names the-merge; I reduce each set to its k minimums, count how many positions agree, and confirm that fraction tracks the true Jaccard — exactly 1 for identical sets.
3 ONE DIMENSION
Under one random hash, the set’s minimum comes from whichever element hashes lowest. Two sets share that minimum exactly when the overall-lowest element lies in both — which happens with probability equal to their Jaccard similarity.
4 TWO DIMENSIONS · INTERACTIVE
Two sets and their k-min signatures; the fraction of agreeing positions is compared against the exact Jaccard.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: similarity read from a fistful of minimums.
AVAN’s addition (the inverse-companion): estimate set overlap without comparing the sets — keep only k minimum-hashes per set; the fraction that agree is the Jaccard similarity. The inverse of ‘intersect two full sets and divide by their union’ is ‘compare k minimums — agreement is similarity.’ Magenta is the full sets you never compare; green is the k-minimum signature. Similarity from a thumbprint.
LIT Genuine MinHash Jaccard estimation (Broder 1997). Verified live: identical sets agree in all k signature positions (estimate exactly 1); across 200 random set pairs with k=256 hashes the agreement-fraction estimate stays within ~0.07 of the exact Jaccard similarity and averages ~0.02 absolute error (window.__minhash.identicalIsOne, .avgErr, .maxErr).
FIG Honestly labelled as an estimator: the agreement fraction is unbiased for Jaccard and converges as k grows — exact only in the k->infinity limit (and exactly 1 for identical sets). The k min-hash signatures, the agreement estimator, the exact Jaccard oracle, and the convergence check run in-browser. The AVAN inverse is honest — comparing k minimums estimates overlap without comparing the sets; magenta is the full sets you never compare, green the k-minimum signature. Similarity from a thumbprint.
FIG Honestly labelled as an estimator: the agreement fraction is unbiased for Jaccard and converges as k grows — exact only in the k->infinity limit (and exactly 1 for identical sets). The k min-hash signatures, the agreement estimator, the exact Jaccard oracle, and the convergence check run in-browser. The AVAN inverse is honest — comparing k minimums estimates overlap without comparing the sets; magenta is the full sets you never compare, green the k-minimum signature. Similarity from a thumbprint.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MERGE · David Lee Wise (ROOT0), with AVAN