Lesson 11.3• 10 min read

Duplicate elimination and SimHash

Duplicate URL elimination, Bloom filters, and 64-bit SimHash fingerprints compared by Hamming distance.

What you will learn

  • Tell duplicate URLs from duplicate content.
  • Normalize URLs, and size a Bloom filter for a billion of them.
  • Detect near-duplicate pages with SimHash, and find fingerprints within kkwhat its symbols mean bits quickly.

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 (the number of features two pages share, divided by the number in either) 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 (short values computed from each URL), not the URLs themselves, mostly on disk with recent entries buffered in memory.

Normalize before comparing, so trivially different spellings count as one URL (URL normalization): 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 in bits for nnwhat its symbols mean items and a false positive rate ppwhat its symbols mean is:

m=−nln⁡p(ln⁡2)2m = -\frac{n \ln p}{(\ln 2)^2}what its symbols mean

For the primer's n=109n = 10^9 links and p=0.001p = 0.001: m≈1.44×1010m \approx 1.44 \times 10^{10}what its symbols mean bits, about 1.8 GB, with h=mnln⁡2≈10h = \frac{m}{n}\ln 2 \approx 10what its symbols mean 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: its words, after case folding (making every letter lower case), stop-word removal (dropping common words such as "the"), stemming (cutting each word down to its stem, so "crawling" becomes "crawl") and so on.
  2. Keep a vector VVwhat its symbols mean of ffwhat its symbols mean counters, all zero.
  3. Hash each feature to ff 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 iiwhat its symbols mean is 1 if V[i]>0V[i] > 0what its symbols mean, 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=3k = 3what its symbols mean are reasonable." Here kk is the largest Hamming distance, the number of bit positions in which two fingerprints differ, still treated as a near-duplicate.


Finding fingerprints within kk bits

Comparing a new fingerprint with billions of stored ones one by one is too slow. Manku et al. use the pigeonhole principle (if more things than boxes are put into boxes, some box holds two). 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 bbwhat its symbols mean bits over 2d2^dwhat its symbols mean fingerprints returns about 2d−b2^{d-b}what its symbols mean per probe. With the paper's 2342^{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 2302^{30} (1 billion) pages, 4 tables keyed on 16 bits still return about 16,000 candidates per table.

64-bit SimHash

Words are the features, weighted by count. Similar pages get fingerprints that differ in few bits; Manku et al. found k = 3 bits reasonable for 8 billion pages.

A = 0x5aa7f254909b6331
0101101010100111111100100101010010010000100110110110001100110001
B = 0x5aa7f25590996331
0101101010100111111100100101010110010000100110010110001100110001
Hamming distance
2 of 64 bits
B is a near-duplicate: skip it
16-bit blocks that match exactly: 1✓2·3·4✓With at most 3 differing bits, at least one of the 4 blocks must match, so 4 tables, each keyed on one block, find every candidate.
Fetchers3× instancesURL check3× instancesSeen-URL set (Bloomfilter)2× instancesFrontier1× instanceContent check(SimHash)3× instancesFingerprint tables2× instancesObject store (uniquepages)1× instanceFetchers3× instancesURL check3× instancesSeen-URL set (Bloomfilter)2× instancesFrontier1× instanceContent check(SimHash)3× instancesFingerprint tables2× instancesObject store (uniquepages)1× instanceFetchers3× instancesURL check3× instancesSeen-URL set (Bloomfilter)2× instancesFrontier1× instanceContent check(SimHash)3× instancesFingerprint tables2× instancesObject store (uniquepages)1× instance
Figure 3

Two checks for duplicates: each new URL against every URL already seen, and each downloaded page against the fingerprints of the pages stored.

Follow a downloaded page. Its links go to the URL check, which normalizes each one and asks the seen-URL set whether it was seen before; only new URLs go on to the frontier. The page itself goes to the content check, which computes its 64-bit SimHash fingerprint and looks in the fingerprint tables for one within 3 bits. A near-duplicate is dropped; any other page is stored and its fingerprint added. The fetchers and both checks are counted for the primer’s 1,600 pages a second at about 1,000 a second per server, plus one spare, each check taking a page’s links or its fingerprint as one request; the seen-URL set and the fingerprint tables are one node each at the lab’s 12,000 a second, plus a spare.

  • Fetchers: 3 × App server
  • URL check: 3 × App server
  • Seen-URL set (Bloom filter): 2 × Cache
  • Frontier: 1 × Queue
  • Content check (SimHash): 3 × App server
  • Fingerprint tables: 2 × Cache
  • Object store (unique pages): 1 × Object store
  • Fetchers sends requests to URL check
  • URL check sends requests to Seen-URL set (Bloom filter)
  • URL check sends requests to Frontier
  • Fetchers sends requests to Content check (SimHash)
  • Content check (SimHash) sends requests to Fingerprint tables
  • Content check (SimHash) sends requests to Object store (unique pages)

Key takeaways

  • Normalize URLs before comparing them, then check each against every URL already queued or downloaded.
  • A Bloom filter for 10910^9 URLs at a 0.1% false positive rate takes about 1.8 GB; it never misses a seen URL but occasionally skips a new one.
  • A cryptographic hash changes completely for a one-byte difference; SimHash gives similar pages fingerprints a few bits apart (64 bits, k=3k = 3what its symbols mean for 8 billion pages).
  • Split the fingerprint into blocks: two within 3 bits must agree exactly on at least one block, so a few tables keyed on blocks find the candidates.
Sources4