AltaVista found near-duplicate pages by sketching their Jaccard resemblance

A search engine's index is full of mirrored and copied pages, and deduplicating them naively means comparing every page to every other — millions squared.

Broder's 1997 work represented a page as a set of shingles, then kept only the handful with the smallest hash under a permutation. Two pages' sets share a minimum value in proportion to their Jaccard resemblance, so a short sketch estimates similarity with no pairwise comparison.

AltaVista used the sketch to cluster the web's near-duplicate pages and drop the copies from results. The method turned an intractable similarity problem into a quick hashing job.

Same small hashes means pages are alike

A few minimum hashes estimate Jaccard similarity with no element-by-element comparison.

The signature is fixed size, so cost per page is tiny and stores well.

It is an unbiased estimator, correct on average across pages.

The same sketch supports near-duplicate detection and clustering at scale.

Do not compare two large sets element by element. Reduce each to a few minimum hashes, so the odds they agree equal the sets' overlap, and the problem turns tiny.

MinHash became a foundation of large-scale near-duplicate detection, set similarity and deduplication in search, advertising and machine learning, and later the locality-sensitive-hashing family built on it.