MinHash, SimHash and LSH

How do you estimate similarity from a fixed-size signature, and escape all-pairs comparison?

MinHash

The identity the whole thing rests on. For a random hash function h (think: a random permutation of all possible elements),

The right-hand side is the Jaccard similarity of the sets (shared items divided by all distinct items, a number from 0 to 1). Why: look at all elements of the union A ∪ B. Each is equally likely to have the smallest hash. The two minima are equal exactly when that overall smallest element lies in both sets, that is, in the intersection.

Use k different hash functions (or the bottom-k of one, which is the KMV structure again) and estimate the similarity J as the fraction of the k positions where the minima match. The error is about 1/√k.

What it converts. Comparing two sets costs O(|A| + |B|). Comparing two MinHash signatures costs O(k), independent of set size. All-pairs similarity changes from "intersect every pair of sets" into "compare every pair of 128-byte signatures".

That is still quadratic in the number of sets. Hence the next section.

---

SimHash and LSH

The constraint this section exists to break. All-pairs similarity is O(n²), and n² is the actual wall in deduplication, entity resolution and near-duplicate detection, which are core data engineering tasks. At n = 10⁷ records, n² is 10¹⁴ comparisons. No amount of per-comparison optimization saves you.

LSH (locality-sensitive hashing) inverts the usual goal of hashing: hash so that similar items collide on purpose. The standard banding construction on a MinHash signature: split the k signature rows into b bands of r rows each. Two items become candidates if any band matches entirely. The probability that two items with similarity J become candidates is

This is an S-shaped curve, and its steepest point (the effective threshold) sits at approximately (1/b)^(1/r). This formula is the design knob, and it is derivable rather than tuned by feel.

SimHash does the same job for angular (cosine) similarity on vectors: project onto random hyperplanes, keep the sign bits, and the Hamming distance (number of differing bits) between two signatures approximates the angle between the vectors. Google's near-duplicate web page detection used 64-bit SimHash with a Hamming threshold of 3.

This is the one place in this article with false negatives, and it should be said plainly. An LSH-based dedup pipeline misses duplicates, and the miss rate is a design parameter set by b and r. Anyone who says "we deduplicate with LSH" has chosen a recall level, whether or not they know they chose it. Compare Bloom, where the error only wasted work. Here the error silently changes the output.

Current engineering reality. For vector similarity search (finding nearest neighbors of an embedding), LSH has largely lost to graph-based methods (HNSW, which navigates a graph of near neighbors) and to quantization methods (IVF-PQ, which cluster vectors and store compressed codes) in practice, despite having the better theory. It survives where you need provable guarantees, streaming insertion without index rebuilds, or very high dimensions. This is a genuine case of the theoretically grounded method losing to the empirically better one.