Near-Duplicate Detection

The web repeats itself. The same news story runs on dozens of sites, the same documentation is mirrored on many servers, and the same page is reachable under several URLs. Manning, Raghavan, and Schütze (2008, §19.6) cite estimates that as many as 40 percent of web pages duplicate other pages. Indexing every copy wastes storage, following the links of every copy wastes crawling, and showing every copy in a result list wastes the searcher's time, which is why web search removes duplicates before showing results. This article describes how duplicates are found, first exact ones and then the much more common near-duplicates.

One small example runs through the article. Two sentences differ in two words:

• $d_1$ = the crawler fetches each page and follows its links to new pages
• $d_2$ = the crawler fetches every page and follows its links to other pages

A reader sees at once that they are nearly the same. The methods below turn that impression into a number, then into a number that can be computed for billions of pages.

Exact duplicates

An exact copy can be found with a fingerprint: a hash of the page's content, such as 64 bits of a cryptographic hash. Two pages with different fingerprints certainly differ. Two pages with the same fingerprint are, with overwhelming probability, identical. The crawler's "content seen?" test keeps the fingerprints of all fetched pages and checks each new page against them.

Exact fingerprints are brittle. A copy that differs only in a date, an advertisement, or a navigation menu gets an entirely different hash. The two example sentences, which share ten of their twelve words, have unrelated fingerprints, so an exact test calls them different documents. Broder, Glassman, Manasse, and Zweig (1997) found many such near-copies in a large web crawl, and exact matching alone misses them.

Shingling

Shingling (Broder, Glassman, Manasse, and Zweig, 1997) compares documents by their overlapping word sequences. The $k$-shingles of a document are its sequences of $k$ consecutive words. For $k = 4$, the document a rose is a rose is a rose has three distinct 4-shingles: a rose is a, rose is a rose, and is a rose is. Each document is represented by its set of shingles, and two documents are compared with the Jaccard coefficient of their sets:

$$J(S_1, S_2) = \frac{\lvert S_1 \cap S_2 \rvert}{\lvert S_1 \cup S_2 \rvert}.$$

Identical documents score 1 and documents with no shingles in common score 0. Pages whose coefficient exceeds a threshold, such as 0.9, are treated as near-duplicates.

The running example

Each example sentence has twelve words and so ten 3-shingles. Together they have 15 distinct shingles, listed here in alphabetical order and numbered for use in the next section:

Five shingles are shared and the union has 15, so $J(d_1, d_2) = 5/15 = 1/3$. The documents share 10 of 12 words, yet their resemblance is only a third. Each changed word destroys every shingle that contains it, which is up to $k$ shingles, so with $k = 3$ two changed words remove five of each sentence's ten shingles. On a sentence this short the effect is drastic. On a page of 2,000 words, the same two edits would remove at most 6 of about 2,000 shingles, and the coefficient would stay near 1. Shingling measures how much text two documents share in the same order, and short documents are fragile under it.

The choice of $k$

As a second example with $k = 3$, take $d_3$ = a rose is a rose is a rose and $d_4$ = a rose is a flower which is a rose. The document $d_3$ has 3 distinct shingles and $d_4$ has 7. They share 3 (a rose is, rose is a, is a rose), and their union has 7, so $J = 3/7 \approx 0.43$. With $k = 2$ the coefficient is $3/6 = 0.5$. Shorter shingles make documents look more alike, since short word sequences are common to many texts, and longer ones make the test stricter. Values of $k$ from about 4 to 10 words are typical.

Estimating resemblance with MinHash

Comparing the full shingle sets of every pair of pages is out of the question for billions of pages. Broder (1997) showed how to estimate the Jaccard coefficient from a small, fixed-size sketch of each document.

Apply a random hash function $h$ to every shingle of both documents and take the minimum hash value of each set. The probability that the two minimums are equal is exactly the Jaccard coefficient:

$$P\left[\min_{s \in S_1} h(s) = \min_{s \in S_2} h(s)\right] = J(S_1, S_2).$$

The argument takes three steps.

1. Look at the shingle $s^*$ with the smallest hash value in the whole union $S_1 \cup S_2$. Since $h$ is random, every shingle of the union is equally likely to be $s^*$.
2. If $s^*$ is in both sets, it is the minimum of each, so the two minimums are equal.
3. If $s^*$ is in only one set, it is the minimum of that set but absent from the other, whose minimum is some larger value. The minimums differ.

So the minimums agree exactly when $s^*$ falls in the intersection, which happens with probability $\lvert S_1 \cap S_2 \rvert / \lvert S_1 \cup S_2 \rvert$. In the running example, $s^*$ is one of 15 shingles, and the minimums agree when it is one of the 5 shared ones.

By hand

To see the procedure on real numbers, number the 15 shingles as in the table and use hash functions of the form $h(x) = (a x + b) \bmod 17$, where $x$ is the shingle's number. Because 17 is prime and $a$ is not a multiple of it, each such function sends the 15 numbers to 15 different values, so it acts as a reordering of the shingles. Six functions give:

For the second row, $h(4) = (3 \cdot 4 + 5) \bmod 17 = 0$, so shingle 4, every page and, has the smallest value in the union. It belongs only to $d_2$, so $d_2$'s minimum is 0, while $d_1$'s smallest value is 3, from shingle 5. The first row is the identity ordering: shingle 0 is shared, so both minimums are 0.

The six functions agree once, an estimate of $1/6 \approx 0.17$ for a true value of $1/3$. Six hash functions are too few for a reliable estimate, which is the point of the next section.

How many hash functions

With $m$ independent hash functions, the sketch of a document is its list of $m$ minimum values, and the estimate of $J$ is the fraction of positions where two sketches agree. Each position agrees with probability $J$, independently of the others, so the number of agreements has a binomial distribution with $m$ trials and success probability $J$. Its mean is $mJ$ and its variance is $mJ(1-J)$. Dividing by $m$, the estimate has mean $J$, so it is unbiased, and standard error

$$\sqrt{\frac{J(1-J)}{m}}.$$

For the running example, $J = 1/3$ gives a standard error of 0.149 with $m = 10$, 0.047 with $m = 100$, and 0.033 with $m = 200$ (rounded to three places). The figure shows 30 independent runs of the estimate, each with its own random hash functions, as $m$ grows.

At $m = 200$, the median estimate over the 30 runs was 0.333 and the middle half of the runs lay between 0.315 and 0.345. Manning, Raghavan, and Schütze (2008, §19.6) use sketches of 200 values. A page of thousands of words is reduced to 200 numbers, and comparing two pages costs 200 comparisons regardless of their length. The sketch size depends on the precision wanted, not on the length of the documents.

Avoiding all pairs

Even with sketches, comparing all pairs is quadratic: a billion pages make about $5 \times 10^{17}$ pairs. Large systems avoid it by grouping sketches that share values, so that only pages likely to be similar are compared at all. Hashing groups of sketch positions together is a form of locality-sensitive hashing.

One common scheme cuts the sketch of $m$ values into $b$ bands of $r$ values each, with $m = br$. Each band is hashed as a whole, and two pages become a candidate pair if they match in every value of at least one band. The probability of that follows from the agreement probability of a single position:

• one band matches in all $r$ positions with probability $J^r$;
• it fails to match with probability $1 - J^r$;
• all $b$ bands fail with probability $(1 - J^r)^b$, since the bands use different hash functions;
• so the pair is compared with probability $1 - (1 - J^r)^b$.

With a 200-value sketch in 20 bands of 10, a pair with $J = 0.9$ is compared with probability 0.9998 and a pair with $J = 0.5$ with probability 0.019. The running example's pair, at $J = 1/3$, is compared with probability 0.0003, so it would almost never be examined. The choice of $b$ and $r$ moves the threshold at which pairs start being compared, roughly to $(1/b)^{1/r}$.

Simhash

A different fingerprint, simhash (Charikar, 2002), maps each document's weighted features to a single short bit string in such a way that documents with high cosine similarity get strings that differ in few bits. Manku, Jain, and Das Sarma (2007, §2) describe the computation for web pages:

1. Extract the page's features, such as its words, each with a weight, such as its count.
2. Hash each feature to an $f$-bit value, with $f = 64$ for example.
3. Keep $f$ running totals, all starting at zero. For each feature and each bit position $i$, add the feature's weight to total $i$ if bit $i$ of the feature's hash is 1, and subtract it if the bit is 0.
4. Bit $i$ of the simhash is 1 if total $i$ is positive, and 0 otherwise.

Each feature votes on every bit, with a strength equal to its weight. Two documents that share most of their features share most of the votes, so most of their totals have the same sign.

By hand

Take $d_1$ with words as features, each with weight 1, and its 12 words hashed to 64 bits by taking the first 64 bits of their MD5 hashes. The first 8 bits of each word's hash, and the resulting totals, are:

In the first position, 8 of the 12 words have a 1 and 4 have a 0, so the total is $8 - 4 = +4$ and the bit is 1. In the second, 5 words have a 1 and 7 a 0, so the total is $-2$ and the bit is 0. The same procedure over all 64 bits gives $d_1$ the fingerprint 93264c674404019d in hexadecimal and $d_2$ the fingerprint 91060e274484039d.

Bits that agree, and angles

The two fingerprints differ in 7 of their 64 bits. Charikar (2002, §3) showed why the number of differing bits measures similarity. If a bit is computed as the sign of the projection of a document's feature vector onto a random direction, then for two documents whose vectors make an angle $\theta$, the bit agrees with probability

$$P[\text{bit agrees}] = 1 - \frac{\theta}{\pi}.$$

The picture is a random plane through the origin. The bit differs only when the plane passes between the two vectors, and that happens with probability $\theta / \pi$. Hashing each feature to $\pm 1$ in every bit position, as step 3 does, is projection onto a random direction whose coordinates are $\pm 1$ rather than normally distributed, so the formula holds approximately.

For the example, the word-count vectors of $d_1$ and $d_2$ share 10 of their 12 words, each with count 1, so their cosine similarity is $10/12 = 0.833$, the angle between them is 33.6 degrees, and the formula predicts that $1 - 33.6/180 = 0.814$ of the bits agree. The observed fraction, $57/64 = 0.891$, is within the variation expected from 64 random bits, whose standard deviation here is about 0.049. For contrast, the unrelated $d_3$ (a rose is a rose is a rose) shares no words with $d_1$, so its vector is at 90 degrees and half the bits should agree. Its fingerprint differs from $d_1$'s in 37 bits, so 27 of 64 agree, 0.42.

Manku, Jain, and Das Sarma (2007) used 64-bit simhash fingerprints to detect near-duplicates among 8 billion web pages, treating two pages as near-duplicates if their fingerprints differed in at most 3 bit positions. By the formula above, 3 of 64 bits are expected to differ when the angle is $3/64 \times 180 \approx 8.4$ degrees, a cosine similarity near 0.99, so the threshold is aimed at pages that are very similar indeed. It is not a sharp cut at that angle: with only 64 bits, pages somewhat further apart sometimes fall within 3 bits, and pages somewhat closer sometimes do not. A single 64-bit fingerprint per page is far more compact than a sketch of 200 values, at the cost of a coarser measure of similarity.

Shingles or simhash

The two methods measure different things. The Jaccard coefficient of shingle sets is sensitive to word order and to every edit, as the running example showed. Simhash over words ignores order, and a short edit to a long page moves the cosine similarity only slightly. A page whose paragraphs have been rearranged keeps nearly the same simhash, but its shingle set changes at every boundary between moved paragraphs.

Duplicates on this site

The pages fetched in the crawl of this site were tested the same way. No two of the 82 pages, crawled before this topic was written, had the same exact fingerprint. For 2,000 randomly sampled pairs of pages, out of 3,321 possible, the 4-shingle Jaccard coefficient was:

The site has no near-duplicates, as expected for a set of distinct articles. The most similar sampled pair was two topic pages, Boolean Retrieval and Text Processing and Indexing, which share structural phrases such as their section headings. Their exact coefficient on main content was 0.036, and a 200-value MinHash sketch estimated it as 0.045, within the expected error of about 0.013.

The navigation and footer raised the similarity of pairs only slightly on average, because they are short compared with the articles. On sites with long menus, sidebars, and footers and short main content, such as product listings, shared boilerplate can make unrelated pages look alike. Extracting the main content before fingerprinting is then important, and it is also the basis of the change detection in monitoring websites.

The worked examples above are computed by tools/experiments/crawling/nearduplicate_math.py in the site repository, and the site measurements by sitecrawl.py in the same folder.

References

• Broder, A. Z. (1997). On the resemblance and containment of documents. In Proceedings of Compression and Complexity of Sequences 1997, 21–29. IEEE.
• Broder, A. Z., Glassman, S. C., Manasse, M. S., and Zweig, G. (1997). Syntactic clustering of the web. Computer Networks and ISDN Systems, 29(8–13), 1157–1166.
• Charikar, M. S. (2002). Similarity estimation techniques from rounding algorithms. In Proceedings of STOC 2002, 380–388.
• Manku, G. S., Jain, A., and Das Sarma, A. (2007). Detecting near-duplicates for web crawling. In Proceedings of WWW 2007, 141–150.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 19.6. Cambridge University Press.