Comparing two small sets is easy. Comparing millions of huge sets is not. If you compare every document, user, or item collection with every other one, the work explodes quickly. MinHash solves this by giving each set a small summary that lets us estimate similarity without comparing the full sets directly.

That small summary is called a signature. If two full sets are similar, their signatures are likely to look similar too. This makes MinHash useful for finding near-duplicate documents, similar users, related search queries, or item collections with a lot of overlap.

MinHash answers a very specific question: not "how many unique items are there?" but "how similar are these two sets?"

This chapter explains the idea behind MinHash, how shingles and signatures work, how MinHash is often paired with locality-sensitive hashing (LSH), and where it works well in real systems.

Suppose a system has millions of documents and needs to find near-duplicates. Comparing every document with every other document is too expensive.

The usual way to measure overlap between two sets is Jaccard similarity:

In plain English, Jaccard similarity means "shared items divided by total unique items across both sets." If two documents share many shingles, their Jaccard similarity is high. If they share only a few, it is low.

The exact calculation needs the full sets. MinHash turns each set into a fixed-size signature that gives a close estimate instead.