The encyclopedia · Software & IT · Technical decision · 1997
AltaVista found near-duplicate pages by sketching their Jaccard resemblance
Broder's 1997 MinHash sketch estimated the Jaccard similarity of huge pages via a few minimum hashes, so AltaVista clustered near-duplicates cheaply.
AltaVista · Digital Equipment Corporation
the move
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.
why it works
- 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.
what transfers
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.
what came after
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.
references
spotted an error? The archive wants to know.