📄 Detecting Near-Duplicates for Web Crawling

Summary

Web crawlers often fetch pages whose main content matches a page already stored, differing only in minor parts such as ads, counters or timestamps. Exact checksums cannot catch these near-duplicates. Skipping them, along with their outgoing links, saves bandwidth and storage, improves index quality and reduces load on remote servers. The obstacle is scale: billions of stored pages and billions of new fetches per day, with decisions needed quickly on few machines.

The authors, working at Google, make two contributions. First, they apply Charikar's simhash to web pages. Weighted features from standard IR preprocessing are compressed into a short fingerprint, and pages with similar content end up with fingerprints that differ in only a few bits. Experiments on a repository of 8B pages support 64-bit fingerprints with a threshold of k = 3 differing bits.

Second, they solve the resulting Hamming Distance Problem. They keep several sorted, compressed copies of the fingerprint table, each with its bits reordered by a different permutation. A query probes these tables in parallel by matching leading bits, then checks the few candidates found. This works for single online lookups and for large batches. The paper also surveys earlier duplicate-detection methods.

Key points

• How simhash works: each feature's hash adds or subtracts that feature's weight across f counters. The sign of each counter then gives the corresponding fingerprint bit. Unlike SHA-1 or MD5, similar inputs produce nearby hash values.
• Target workload: 8B 64-bit fingerprints, about 64GB in total.
  • Online queries must be answered within milliseconds for k = 3.
  • Batch mode handles about 1M queries in roughly 100 seconds, which is about 1B queries per day.
• Why simple approaches fail: probing every fingerprint within distance 3 would take 41,664 lookups per query. Precomputing all such neighbours would multiply storage by up to that factor. The permuted-table design sits between these extremes and allows a trade-off between query time and memory.
• Fingerprint size: simhash needs only 8 bytes per page, compared with 24 bytes for Broder's shingle-based fingerprints. The authors used Charikar's original C++ implementation, and Henzinger (SIGIR 2006) compared the two methods.
• Practical use: in a real crawler, a near-duplicate signal may serve as one factor in a URL's crawl priority rather than a strict keep-or-drop rule.