MinHash and locality-sensitive hashing

Why it matters

A search engine must drop near-duplicate pages, a marketplace must find listings copied from each other, a recommender must find users with similar histories, and a spam filter must cluster messages that differ by a few words. All are "find pairs that are similar" over millions or billions of items, and comparing every pair is quadratic and hopeless. MinHash compresses each item into a short signature whose agreement estimates similarity, and locality-sensitive hashing turns "find similar items" into "look up the same bucket". It is the technique behind near-duplicate detection at web scale.

The idea

Represent each item as a set: a document as its set of word shingles (overlapping runs of k words), a user as the set of items they interacted with. The Jaccard similarity of two sets is the size of their intersection divided by the size of their union: 1 for identical, 0 for disjoint.

MinHash estimates Jaccard without the sets. Pick a hash function and define an item's minhash as the minimum hash value over its set's elements. For two sets, the probability that their minhashes are equal is exactly their Jaccard similarity, because the element with the overall smallest hash across the union is equally likely to be any element, and the minhashes agree exactly when that element lies in the intersection. Repeat with 100 or 200 independent hash functions to get a signature; the fraction of positions that agree estimates the similarity.

From signatures to candidates: banding

Signatures shrink each item to a few hundred bytes, but finding similar pairs still looks quadratic. Locality-sensitive hashing (LSH) by banding fixes it: split each signature of n slots into b bands of r rows; hash each band to a bucket; two items become a candidate pair if any band lands in the same bucket. Items with high similarity agree on whole bands often and collide somewhere; dissimilar items rarely do. With b of 20 and r of 5 (a 100-slot signature), pairs at 0.8 similarity are found with over 99 percent probability while pairs at 0.3 collide under 5 percent of the time. Candidates are then verified with the full signature or the original sets.

Step	Input	Output	Cost
Shingle	Document	Set of k-shingles (hashed to integers)	Linear in document length
MinHash	Set	Signature of n minima	n hashes per element; done once per item
Band and bucket	Signature	b bucket ids	b hashes; insert into b hash tables
Candidate pairs	Bucket collisions	Pairs to verify	Proportional to true near-duplicates plus a few false candidates
Verify	Candidate pair	Similarity	Compare signatures or sets

Tuning the threshold

The similarity at which a pair becomes likely to collide is roughly 1 over b raised to 1 over r. More bands with fewer rows find lower similarities (more candidates, more false positives); fewer bands with more rows demand higher similarity (fewer candidates, more misses). Choose by the similarity you call "duplicate" and the cost of verifying candidates.

Relatives

SimHash produces a fingerprint whose Hamming distance tracks cosine similarity of weighted features and was used by Google for web deduplication. Random projection LSH handles dense vectors under cosine or Euclidean distance; for embedding search at scale, the graph and clustering indexes from the vector databases lesson have largely taken over, but LSH remains the simple, mergeable, streaming-friendly option. Bloom filters answer membership, HyperLogLog counts distincts; MinHash answers similarity between sets.

Where it is used

Near-duplicate detection in web crawls and content moderation, plagiarism and clone detection, deduplicating training data for machine-learning models, similar-user and similar-item candidate generation in recommenders, record linkage across databases with noisy fields, and malware clustering. In each case the win is turning a pairwise problem into a per-item one.