Every other entry in this site's Probabilistic category answers a question about one item at a time: is this item in the set, roughly how many times has it appeared, roughly how many distinct items are there, is this item one of the k I should keep. Locality-Sensitive Hashing (LSH) answers a question about pairs: are these two things approximately the same — and, at real scale, which pairs among millions are even worth checking, without comparing every pair directly. The version built here is MinHash, the classic instance (Broder, 1997, originally for detecting near-duplicate web pages at AltaVista) for estimating Jaccard similarity — the size of two sets' intersection divided by the size of their union — between sets that might each be too large, or too numerous, to compare pairwise in full.
Represent each item as a set — this page uses the set of distinct words in a sentence, but the same idea works on k-grams of a document, k-mers of a genome, or any other "shingling" of an item into a set. Now pick k independent hash functions. For one hash function and one set, the MinHash value is the smallest hash any member of the set produces. Do this for all k hash functions and a set's signature is the k resulting minimums — always exactly k numbers, whether the underlying set has 5 elements or 5 million.
The reason this works is a fact about random hash functions, not a heuristic: for one
hash function drawn uniformly at random, the probability that two sets A and B land on the
same minimum element is exactly their Jaccard similarity, |A∩B| / |A∪B| —
whichever element of the combined set A∪B happens to hash lowest is equally likely to be any one
of them, and it's a shared minimum exactly when that lowest-hashing element belongs to both sets.
Run k independent hash functions and count how many of the k signature slots agree: that fraction
is an unbiased estimate of the true Jaccard similarity, with error shrinking as k grows (see
Pitfalls for exactly how much).
A signature alone already compresses two sets of any size down to two rows of k small numbers
each. Banding is what turns that into a way to avoid checking every pair in
the first place: split each k-long signature into b bands of r rows each
(k = b·r), and hash every document's per-band slice into a bucket. Two documents
become candidates the moment they land in the same bucket in at least one band —
only candidate pairs ever get compared further. Similar documents, which agree on many signature
slots, are likely to agree on an entire band somewhere and land together; dissimilar documents,
which rarely agree on more than a slot or two, are unlikely to ever share a full band. That's the
"locality-sensitive" part of the name: nearby items collide more than far-apart ones, on purpose.
Eight sample sentences are loaded (word sets, lowercase, punctuation stripped) — three near-duplicate pairs (an exact repeat and two paraphrases) among otherwise unrelated ones. Pick any two and compare: the signature table shows all k = 16 MinHash values for each document side by side, with agreeing slots highlighted, next to the estimate those agreements imply and the true Jaccard similarity computed directly from the word sets for comparison.
The same k = 16 signatures, split into bands of different shapes. Strict (1 band of all 16 rows) requires a full signature match — nothing short of a near-exact duplicate ever lands together. Loose (16 bands of 1 row each) only needs a single matching slot in any one of the 16 bands — almost everything ends up a candidate. Balanced (4 bands of 4 rows) sits between them. Switch schemes and watch which pairs get flagged as candidates, against the three pairs that are actually similar (true Jaccard ≥ 0.5): 0↔1, 0↔6, 1↔6.
O(k · |set|),
independent of how the set will later be compared to anything else.O(k), needs neither original set again.O(n · b) total across n documents (a hash-map insert per document per
band) instead of the O(n²) a brute-force all-pairs comparison would cost.function fnv1a(s) {
let h = 0x811c9dc5;
for (let i = 0; i < s.length; i++) {
h ^= s.charCodeAt(i);
h = Math.imul(h, 0x01000193);
}
return h >>> 0;
}
// k independent-ish hash functions from one affine family, h_i(x) = (a_i*x + b_i) mod P,
// with a_i/b_i drawn from a seeded xorshift32 stream so the whole demo is reproducible.
const MERSENNE_LIKE_PRIME = 4294967311n; // smallest prime above 2^32
function makeHashFns(k, seed) {
let s = seed >>> 0;
function next() { s ^= s << 13; s >>>= 0; s ^= s >>> 17; s ^= s << 5; s >>>= 0; return s; }
const fns = [];
for (let i = 0; i < k; i++) {
const a = BigInt((next() % 4294967290) + 1);
const b = BigInt(next() % 4294967290);
fns.push(x => Number((a * BigInt(x) + b) % MERSENNE_LIKE_PRIME));
}
return fns;
}
function signature(wordSet, hashFns) {
const sig = new Array(hashFns.length).fill(Infinity);
for (const word of wordSet) {
const base = fnv1a(word);
for (let i = 0; i < hashFns.length; i++) {
const v = hashFns[i](base);
if (v < sig[i]) sig[i] = v;
}
}
return sig;
}
function estimateJaccard(sigA, sigB) {
let matches = 0;
for (let i = 0; i < sigA.length; i++) if (sigA[i] === sigB[i]) matches++;
return matches / sigA.length;
}
function candidatePairs(signatures, b, r) {
const found = new Set();
for (let band = 0; band < b; band++) {
const buckets = new Map();
for (let d = 0; d < signatures.length; d++) {
const key = signatures[d].slice(band * r, band * r + r).join(',');
if (!buckets.has(key)) buckets.set(key, []);
buckets.get(key).push(d);
}
for (const docs of buckets.values()) {
if (docs.length < 2) continue;
for (let i = 0; i < docs.length; i++)
for (let j = i + 1; j < docs.length; j++)
found.add(`${docs[i]}-${docs[j]}`);
}
}
return [...found];
}Verified standalone in Node before writing any page content, against the exact eight sample
sentences shown above (word-set shingling, k = 16, seed 12345 for the hash-function family — the
same values the live demo uses). The true Jaccard matrix computed directly from the word sets
puts the three real near-duplicate pairs at 0.71 (paraphrase), 1.00 (exact repeat, doc 6 is a
verbatim copy of doc 0), and 0.71 again (0↔6's transitive pair, 1↔6) — everything else at 0.16 or
below. At this exact configuration the balanced scheme (4 bands of 4) finds precisely those three
pairs as candidates and nothing else. Swept the estimator's own accuracy across 100 independent
hash-function seeds (not just the one the demo displays) at several values of k: mean absolute
error against true Jaccard was 0.098 at k=4, 0.070 at k=8,
0.049 at k=16, 0.034 at k=32, 0.026 at k=64,
and 0.018 at k=128 — each doubling of k cuts error by roughly 1/√2,
consistent with MinHash's known variance scaling and cited directly in Pitfalls below, not
estimated after the fact. A separate 200-seed sweep measured recall and false-positive rate for
all three banding schemes against the fixed "true Jaccard ≥ 0.5" threshold — also cited directly
in Pitfalls.
Few hash functions means a genuinely noisy estimate, not just a rounding
error. MinHash's per-pair error behaves like a coin-flip average: standard error scales
as roughly 1/√k. Measured directly (100 seeds, all eight sample documents' pairs):
mean absolute error against true Jaccard was 0.098 at k=4 and only 0.018 at k=128 — a 13x jump in
hash functions for roughly a 5.4x drop in error, not a proportional one. There's no way to shrink
a signature's error after computing it without recomputing with more hash functions from
scratch — same one-way trade every fixed-size sketch on this site makes.
The band/row split controls a real recall-vs-false-positive trade, not a cosmetic knob. Measured across 200 seeds against this page's fixed eight documents and their three true near-duplicate pairs: the strict scheme (1 band of 16 rows, needs a full signature match) found only 34% of the real near-duplicate pairs (204 of 600 seed-pair instances) but never once flagged an unrelated pair — 0 false positives out of 5,000 dissimilar-pair instances checked. The loose scheme (16 bands of 1 row, needs just one matching slot anywhere) caught every real pair without exception (600 of 600) but flagged 59% of unrelated pairs too (2,954 of 5,000) — barely better than comparing everything to everything, defeating the point of banding. The balanced scheme (4 bands of 4) sits between them: 80% recall (482 of 600), 0.6% false-positive rate (29 of 5,000). More bands with fewer rows each catches more real pairs at the cost of more candidates to verify by hand afterward; fewer bands with more rows each verifies more strictly but starts missing real matches — there's no shape that maximizes both at once, only a trade to pick deliberately for the corpus and threshold at hand.
The affine hash family used here is a cheap stand-in for a truly random permutation,
not the real thing. Textbook MinHash assumes each hash function behaves like a uniformly
random permutation of every possible element; this page's (a·x + b) mod P family
(the same "universal hashing" trick Perfect
Hashing uses for its own second-level tables) is a well-known, cheap approximation, not a
literal permutation — good enough that the accuracy numbers above land close to the theoretical
1/√k curve, but a production system handling adversarial input would want a stronger family or a
larger prime modulus than the demo's 33-bit one.
Every other Probabilistic entry on this site spends randomness on a single item at a time — membership (Bloom Filter, Cuckoo Filter), frequency (Count-Min Sketch), distinct count (HyperLogLog), fair sampling (Reservoir Sampling), or balanced search (Skip List, Treap). Locality-Sensitive Hashing spends the same kind of randomness on a question about relationships between items instead — a genuinely different job, not a variation on any of the above.
Time: computing one item's signature is O(k · |shingles|) — k
hash evaluations per shingle. Estimating one pair from their signatures is O(k).
Generating candidates across n items via banding is O(n · b) total (one hash-map
insert per item per band), against the O(n²) a brute-force all-pairs comparison
costs — the entire reason to band at all once n is large. Space: O(k)
per item for its signature, regardless of the underlying set's size, plus O(n) across
the band hash tables.
This site's guide, Choosing a Probabilistic Structure, names this entry as a third, unrelated job alongside the balanced-tree and stream-summarization families it already compares.