This site's Locality-Sensitive Hashing page signs a set down to k numbers and estimates Jaccard similarity from how many of them agree. SimHash (Moses Charikar, 2002) answers a related but genuinely different question: given a weighted vector — a document's word counts, a user's weighted tag list, anything where how much a feature is present matters, not just whether it's present at all — estimate the cosine similarity between two such vectors from a fixed-size bit fingerprint, without ever storing or comparing the full vectors.
The trick rests on a fact about random hyperplanes, not a heuristic. Pick a vector
r whose coordinates are each drawn independently and uniformly from
{+1, −1}, and "project" two vectors u and v onto it by
taking the sign of each one's dot product with r. Charikar's theorem says the
probability that sign(u·r) ≠ sign(v·r) is exactly θ(u,v)/π, where θ is
the angle between u and v — vectors that are close in angle are correspondingly unlikely to land
on opposite sides of a random hyperplane. Repeat with b independent random
hyperplanes and every vector gets a b-bit fingerprint, one sign bit per hyperplane;
the fraction of fingerprint bits where two items disagree is an unbiased estimate of
θ/π, and cos(π · hammingDistance / b) turns that back into an estimated
cosine similarity.
Computing that literally — materializing a real b-dimensional random vector per
hyperplane — is wasteful for a sparse, high-dimensional input (one coordinate per unique word in a
vocabulary that can run into the millions, almost all zero for any one document). SimHash's actual
trick avoids ever building one: for a vector that's a weighted sum of a handful of "present"
features, a random hyperplane's dot product with it reduces to summing the hyperplane's own
random coordinates at exactly those present positions, each scaled by its feature's weight.
So instead of a real random vector, hash each present feature directly to b
pseudo-random sign bits (one per output position), scale each by that feature's own weight, and
add or subtract into a running b-slot accumulator depending on the bit. The
accumulator's final sign per slot is exactly what the real projection's sign would have been —
same math, but O(b) per feature actually present in the item, not
O(b) per dimension in the whole vocabulary.
The same eight sample documents LSH's own page uses, here represented as weighted word-count vectors instead of plain word sets — two paraphrase pairs whose word choice and emphasis both shift a little, one exact repeat, and otherwise-unrelated topics. Pick any two: the fingerprint table shows all b = 32 sign bits for each document side by side, agreeing bits highlighted, next to the Hamming-distance estimate and the true cosine similarity computed directly from the weighted vectors for comparison.
The same b = 32 fingerprints, split into different numbers of equal-size blocks. Two documents become candidates the moment their fingerprints match exactly in at least one block — the same "only compare candidates further" idea as LSH's banding, just keyed off literal block equality instead of a hashed-band match. Strict (1 block of all 32 bits) requires a full fingerprint match — only exact or near-exact duplicates ever land together. Loose (8 blocks of 4 bits) needs just one matching 4-bit block anywhere. Balanced (4 blocks of 8 bits) sits between them. Switch schemes and watch which pairs get flagged as candidates, against the four pairs that are actually similar (true cosine ≥ 0.5): 0↔1, 0↔6, 1↔6, 2↔3.
b pseudo-random sign bits, scale by that feature's own weight, and accumulate into
a b-slot running total; the final fingerprint is the sign of each slot.
O(b · |present features|), independent of how large the whole vocabulary is.π · d / b) and then a cosine of that
angle. O(b), needs neither original vector again.numBlocks equal blocks, group documents by exact block value, and collect every
pair that ever shares a block. O(n · numBlocks) total across n documents, against
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;
}
function xorshift32(seed) {
let s = seed >>> 0 || 1;
return function next() {
s ^= s << 13; s >>>= 0;
s ^= s >>> 17;
s ^= s << 5; s >>>= 0;
return s;
};
}
// b pseudo-random sign bits for one feature, salted by a global seed — stands in for that
// feature's own coordinate on b independent random hyperplanes, without building any of them
function featureBits(feature, seed, b) {
const rng = xorshift32(fnv1a(feature + ':' + seed));
const bits = new Array(b);
let word = 0, have = 0;
for (let i = 0; i < b; i++) {
if (have === 0) { word = rng(); have = 32; }
bits[i] = word & 1;
word >>>= 1; have--;
}
return bits;
}
function fingerprint(weightedVec, b, seed) {
const acc = new Array(b).fill(0);
for (const [feature, weight] of Object.entries(weightedVec)) {
const bits = featureBits(feature, seed, b);
for (let i = 0; i < b; i++) acc[i] += bits[i] ? weight : -weight;
}
let fp = 0n;
for (let i = 0; i < b; i++) if (acc[i] > 0) fp |= (1n << BigInt(i));
return fp;
}
function hammingDistance(fpA, fpB) {
let x = fpA ^ fpB, count = 0;
while (x > 0n) { count += Number(x & 1n); x >>= 1n; }
return count;
}
function estimateCosine(fpA, fpB, b) {
return Math.cos(Math.PI * hammingDistance(fpA, fpB) / b);
}Verified standalone in Node before any page prose was written, against the exact eight sample
documents shown above (weighted word-count vectors, b = 32, seed 12345 — the same values the live
demo uses). True cosine similarity, computed directly from the vectors: 0↔1 (paraphrase) 0.942,
2↔3 (paraphrase) 0.942, 0↔6 (exact repeat) 1.000, 1↔6 (transitively similar) 0.942, every other
pair well below 0.5. At this exact configuration the fingerprint estimates land at 0.882 for
0↔1 and 1↔6 (Hamming distance 5 of 32), 0.924 for 2↔3 (Hamming distance 4), and exactly 1.000 for
0↔6 (Hamming distance 0, identical vectors hash identically) — within a few hundredths of the true
values in every case. Swept the estimator's own accuracy across 300 independent hash-function
seeds (not just the one the demo displays) at several values of b: mean absolute error against
true cosine was 0.350 at b=8, 0.262 at b=16,
0.190 at b=32, 0.137 at b=64, 0.097 at b=128,
0.069 at b=256, and 0.050 at b=512 — each doubling of b cuts
error by roughly 1/√2, the same scaling LSH's own signature length shows, cited
directly in Pitfalls below, not estimated after the fact. A separate 300-seed sweep measured
recall and false-positive rate for all three blocking schemes against the fixed "true cosine ≥
0.5" threshold — also cited directly in Pitfalls.
Dropping per-feature weights quietly turns SimHash into a worse version of the plain set-based signature LSH already builds — the entire reason to reach for this page over that one in the first place. Documents 0 and 1 (and 2 and 3) above are paraphrases that use almost the same words but emphasize them differently — exactly the case a weighted comparison is supposed to get right and a set-only comparison can't see at all. Measured directly on this page's own near-duplicate pairs (0↔1 and 2↔3, averaged over 300 hash-function seeds at b=32): a correctly-weighted fingerprint's mean absolute error against true cosine was 0.048; an unweighted fingerprint (every present feature contributes ±1 regardless of its real weight — exactly what a plain set-based signature already does) rose to 0.086, roughly 1.8x worse. Not a total collapse like Alias Method's forgotten-scale bug on this site — the estimator still runs and still returns a number in range — but a real, consistent accuracy loss specifically on the pairs where weight differences are the whole signal. At this page's own displayed seed (12345) the effect is sharper: doc 0 and doc 1's true cosine is 0.942; the correctly-weighted fingerprint estimates 0.882 (off by 0.06); the unweighted one estimates 0.634 (off by 0.31) — badly understating a genuine near-duplicate pair as barely related.
| pair | true cosine | weighted (mean abs error) | unweighted (mean abs error) |
|---|---|---|---|
| Not run yet — click above. | |||
Too few fingerprint bits means a genuinely noisy estimate, not just a rounding error. SimHash's per-pair error behaves like LSH's own: standard error shrinks with more bits, but there's no way to sharpen an already-computed fingerprint short of rebuilding it from scratch with a larger b. The 300-seed sweep cited above puts mean absolute error at 0.350 for b=8 down to 0.050 for b=512 — real accuracy, but bought with 64x the fingerprint size, a one-way trade like every fixed-size sketch on this site makes.
| b (bits) | mean abs error vs. true cosine |
|---|---|
| Not run yet — click above. | |
Time: computing one item's fingerprint is O(b · |present
features|) — b pseudo-random bits generated per present feature, not per dimension in the
whole vocabulary, which is exactly what makes this cheap on sparse, high-dimensional input.
Estimating one pair from their fingerprints is O(b) — in a real 64-bit implementation
this is a single XOR plus a hardware popcount, both effectively O(1). Generating candidates across
n items via blocking is O(n · numBlocks) total, against the O(n²) a
brute-force all-pairs comparison costs. Space: O(b) bits per item
for its fingerprint, regardless of the underlying vector's dimensionality, plus O(n)
across the block hash tables.
This site's guide, Choosing a Probabilistic Structure, pairs this entry head to head with Locality-Sensitive Hashing — same underlying trick (a fixed-size signature that preserves similarity, block/band-based candidate pruning), applied to weighted vectors and cosine similarity instead of sets and Jaccard similarity.