Duplicate elimination and SimHash

Two kinds of duplicate

• Duplicate URLs: the same link found on many pages. Download it once.
• Duplicate content: different URLs serving the same or nearly the same page, such as mirrors, syndicated articles, or pages that differ only in an advert. Manku, Jain and Das Sarma open their paper with "Near-duplicate web documents are abundant", and note that such differences "are irrelevant for web search".

The primer covers both. Remove duplicate URLs, with sort | unique for small lists or MapReduce at 1 billion links. Detect duplicate content by comparing page signatures for similarity, for example with the Jaccard index or cosine similarity.

Duplicate URLs

Mercator's duplicate URL eliminator checks each extracted URL against every URL "in the URL frontier or [that] has already been downloaded". Only new ones go to the frontier. It stores fixed-size fingerprints of URLs, not the URLs themselves, mostly on disk with recent entries buffered in memory.

Normalize before comparing, so trivially different spellings count as one URL: lower-case the scheme and host, drop default ports and #fragments, and resolve relative links. Stripping known tracking parameters is a policy choice, because some query parameters do change the page.

A Bloom filter (chapter 6) can answer "seen before?" in memory. Its size for $n$ items and false-positive rate $p$ is:

For the primer's $n = 10^9$ links and $p = 0.001$: $m \approx 1.44 \times 10^{10}$ bits, about 1.8 GB, with $k = \frac{m}{n}\ln 2 \approx 10$ hash functions. A Bloom filter never says "new" for a URL it has seen. But it wrongly says "seen" for about 0.1% of new URLs, and those pages are skipped. Whether that is acceptable is a product decision.

Near-duplicate content: SimHash

A cryptographic hash such as MD5 or SHA-1 cannot detect near duplicates. In Manku et al.'s words, two documents that differ in a single byte hash "into two completely different hash-values".

SimHash (Charikar) is built so that similar documents get similar fingerprints. As Manku et al. apply it to web pages:

1. Turn the page into weighted features (tokens after case folding, stop-word removal, stemming and so on).
2. Keep a vector $V$ of $f$ counters, all zero.
3. Hash each feature to $f$ bits. Where a bit is 1, add the feature's weight to that counter; where it is 0, subtract it.
4. The fingerprint's bit $i$ is 1 if $V[i] > 0$, otherwise 0.

Near-duplicates' fingerprints differ in only a few bit positions. Manku et al. "experimentally validate that for a repository of 8B webpages, 64-bit simhash fingerprints and $k = 3$ are reasonable." Here $k$ is the largest Hamming distance still treated as a near-duplicate.

Finding fingerprints within $k$ bits

Comparing a new fingerprint with billions of stored ones one by one is too slow. Manku et al. use the pigeonhole principle. Split the 64 bits into blocks: if two fingerprints differ in at most 3 bits, then with 4 blocks of 16 bits, at least one block is identical. Keep one table per block, sorted by that block, and look the new fingerprint up in each.

Each lookup still returns a group of candidates to check. A table keyed on $p$ bits over $2^d$ fingerprints returns about $2^{d-p}$ per probe. With the paper's $2^{34}$ (8 billion) fingerprints, 4 tables keyed on 16 bits return about 256K candidates per probe. 16 tables keyed on 28 bits return about 64. More tables mean less work per query but more memory, and the paper works through this trade-off. For the primer's $2^{30}$ (1 billion) pages, 4 tables keyed on 16 bits still return about 16,000 candidates per table.