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 kwhat 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 nwhat its symbols mean items and a false positive rate pwhat its symbols mean is:
m=−(ln2)2nlnpwhat its symbols mean
For the primer's n=109 links and p=0.001: m≈1.44×1010what its symbols mean bits, about 1.8 GB, with h=nmln2≈10what its symbols meanhash 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 bytehash "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:
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.
Keep a vector Vwhat its symbols mean of fwhat its symbols mean counters, all zero.
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.
The fingerprint's bit iwhat its symbols mean is 1 if V[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=3what its symbols mean are reasonable." Here k is the largest Hamming distance, the number of bit positions in which two fingerprints differ, 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 (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 bwhat its symbols mean bits over 2dwhat its symbols mean fingerprints returns about 2d−bwhat its symbols mean per probe. With the paper's 234 (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 230 (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.
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× 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 109 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=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.