MinHash / LSH

For each of k independent hash functions, a MinHash signature keeps the minimum hash value seen across every element added to the set. A classic result (Broder, 1997) shows that, under a random permutation of all possible elements, the minimum element of A ∪ B falls in A ∩ B with probability exactly |A∩B| / |A∪B|: the Jaccard similarity. So P(minhash_i(A) == minhash_i(B)) = Jaccard(A, B) for each hash function, and averaging agreement across k independent hashes gives an unbiased estimate with standard error ≈ √(J(1−J)/k).

This is what makes MinHash useful at scale: comparing two 32-number signatures is far cheaper than comparing two full sets, and you never need to bring both original sets into memory at once. LSH takes this further by splitting each signature into bands and bucketing items so that only likely-similar pairs are ever compared directly, turning an O(n²) all-pairs comparison into something close to linear.