How does a web crawler detect near-duplicate pages that an exact content hash misses?

seniorshould knowfreq 40%

answer

one byte flips a digest
similar input, similar fingerprint
weighted features vote per bit
Hamming distance, few bits
pigeonhole: split into k plus 1

basics

~20 s

An exact hash such as SHA-256 changes completely when one byte changes, like a timestamp or an ad. SimHash or MinHash fingerprints stay close for similar pages, so near-duplicates show up as a small Hamming distance or a high estimated Jaccard similarity.

solid answer

~50 s

An exact digest of the body catches byte-identical mirrors, but most duplicates differ in a date, a counter or an ad, and any change gives an unrelated digest. SimHash instead extracts weighted features (tokens or shingles), hashes each to 64 bits, adds the weight at every position where a feature's bit is 1 and subtracts it where it is 0, then keeps the sign of each total. Similar feature sets give fingerprints that differ in few bits, and pages within a small Hamming distance (a few bits, for example 3 of 64) count as near-duplicates. To search billions of fingerprints, split each into 4 blocks: two fingerprints within 3 bits agree exactly on at least one block, so each block can be an exact-match index. MinHash estimates the Jaccard similarity of shingle sets instead. Strip boilerplate first, or template-heavy pages look alike.

An exact digest of the body catches byte-identical mirrors, but most duplicates differ in a date, a counter or an ad, and any change gives an unrelated digest. **SimHash** instead extracts weighted features (tokens or shingles), hashes each to 64 bits, adds the weight at every position where a feature's bit is 1 and subtracts it where it is 0, then keeps the sign of each total. Similar feature sets give fingerprints that differ in few bits, and pages within a small Hamming distance (a few bits, for example 3 of 64) count as near-duplicates. To search billions of fingerprints, split each into 4 blocks: two fingerprints within 3 bits agree exactly on at least one block, so each block can be an exact-match index. **MinHash** estimates the Jaccard similarity of shingle sets instead. Strip boilerplate first, or template-heavy pages look alike.

code

pseudocode · 14 lines

pseudocode

function simhash(features):          // list of (feature, weight)
  v = array of 64 zeros
  for (f, w) in features:
    h = hash64(f)
    for i in 0..63:
      if bit(h, i) == 1: v[i] = v[i] + w
      else:              v[i] = v[i] - w
  fp = 0
  for i in 0..63:
    if v[i] > 0: fp = setBit(fp, i)
  return fp

function isNearDuplicate(a, b, k = 3):
  return popcount(a XOR b) <= k

go deeper

for a junior

Recall that an exact hash only catches identical pages, and that near-duplicates need a similarity-preserving fingerprint.

for a middle

Explain how SimHash builds its bits from weighted feature votes and how Hamming distance measures similarity.

for a senior

Show how to search billions of fingerprints with the block trick, strip boilerplate, pick canonical copies, and use duplicate rates as a crawl signal.

for a principal

Weigh SimHash's compactness against MinHash's tunable accuracy, and own the threshold choice by its cost in lost pages versus duplicate index entries.

Why exact hashing is not enough

A web crawler fetches the same content under many URLs: mirrors, syndicated articles, printer-friendly versions, pages that differ only in a visit counter, a timestamp or a rotating ad. Indexing each copy wastes storage and fills search results with repeats.

The cheap first step is an exact content fingerprint, such as a SHA-256 digest of the page body. It catches byte-identical copies perfectly. But a cryptographic hash is designed so that changing a single byte produces an unrelated digest, so a page with a different date in its footer looks completely new. Catching near-duplicates needs a fingerprint where similar input gives similar output: a locality-sensitive fingerprint.

SimHash: one 64-bit value per page

SimHash turns a page into a short fingerprint whose bits agree with a similar page's bits in most positions.

Extract features from the main text: words or shingles (overlapping runs of k words), each with a weight such as its frequency.
Hash each feature to 64 bits with an ordinary hash function.
Keep a vector of 64 counters. For each feature, at every bit position add the feature's weight if that bit is 1 and subtract it if the bit is 0.
The final fingerprint has bit i set if counter i ended positive.

Changing a few features shifts only a few counters across zero, so similar pages end up with fingerprints that differ in few positions. Similarity is measured as Hamming distance, the number of differing bits. A commonly cited threshold for 64-bit fingerprints of web pages is a distance of about 3 or less, but the right value is tuned on the crawler's own data.

Two cautions: a distance of zero does not prove the pages are byte-identical (use the exact digest for that), and very short pages give noisy fingerprints because few features vote.

Searching billions of fingerprints

Comparing a new fingerprint against every stored one is impossible at web scale. The standard trick uses the pigeonhole principle:

Split each 64-bit fingerprint into k + 1 blocks. For k = 3 that is 4 blocks of 16 bits.
If two fingerprints differ in at most 3 bits, those bits touch at most 3 blocks, so at least one block matches exactly.
Build one exact-match index per block (or one sorted table per permutation that brings a block to the front).
For a new page, look up each of its blocks, then compute the full Hamming distance only on the candidates that share a block.

The cost is storage: with 10 billion pages at 8 bytes per fingerprint, each table is about 80 GB, so four tables are about 320 GB before overhead. That is the price of turning a full scan into a few indexed lookups.

MinHash: estimating set overlap

MinHash answers a slightly different question: how much do two pages' shingle sets overlap, measured as Jaccard similarity (size of intersection divided by size of union)?

Apply many independent hash functions to every shingle and keep the minimum value for each function.
For any one hash function, the probability that two sets share the same minimum equals their Jaccard similarity, so the fraction of matching minimums estimates it.
Banding (a form of locality-sensitive hashing) groups the minimums into bands; pages sharing any whole band become candidates, which avoids pairwise comparison.

Technique	Catches	Size per page	Similarity measure
SHA-256 digest	exact copies only	32 bytes	equal or not
SimHash	small edits across the page	8 bytes (64 bits)	Hamming distance
MinHash	set overlap, including partial copies	many hash values (e.g. 100 or more)	estimated Jaccard

SimHash is favoured where compactness at billions of pages matters most; MinHash gives a more direct, tunable similarity estimate at a higher storage cost.

Making it work in production

Strip boilerplate first. Navigation, footers and templates can dominate a short page, so two different articles on one site would look alike. Fingerprint the main content.
Choose a canonical copy. Keep one member of each cluster, for example the most important or shortest URL, and skip indexing the rest.
Use it as a crawl signal. A host that produces many URLs with the same fingerprint is likely generating variants or a trap; its priority or budget can be lowered, and a normalisation rule can be learned.
Tune on labelled pairs. Too loose a threshold merges genuinely different pages; too strict leaves duplicates in the index.

## Why exact hashing is not enough A web crawler fetches the same content under many URLs: mirrors, syndicated articles, printer-friendly versions, pages that differ only in a visit counter, a timestamp or a rotating ad. Indexing each copy wastes storage and fills search results with repeats. The cheap first step is an **exact content fingerprint**, such as a SHA-256 digest of the page body. It catches byte-identical copies perfectly. But a cryptographic hash is designed so that changing a single byte produces an unrelated digest, so a page with a different date in its footer looks completely new. Catching **near-duplicates** needs a fingerprint where *similar input gives similar output*: a **locality-sensitive** fingerprint. ## SimHash: one 64-bit value per page **SimHash** turns a page into a short fingerprint whose bits agree with a similar page's bits in most positions. 1. Extract **features** from the main text: words or shingles (overlapping runs of k words), each with a weight such as its frequency. 2. Hash each feature to 64 bits with an ordinary hash function. 3. Keep a vector of 64 counters. For each feature, at every bit position add the feature's weight if that bit is 1 and subtract it if the bit is 0. 4. The final fingerprint has bit i set if counter i ended positive. Changing a few features shifts only a few counters across zero, so similar pages end up with fingerprints that differ in few positions. Similarity is measured as **Hamming distance**, the number of differing bits. A commonly cited threshold for 64-bit fingerprints of web pages is a distance of about 3 or less, but the right value is tuned on the crawler's own data. Two cautions: a distance of zero does not prove the pages are byte-identical (use the exact digest for that), and very short pages give noisy fingerprints because few features vote. ## Searching billions of fingerprints Comparing a new fingerprint against every stored one is impossible at web scale. The standard trick uses the **pigeonhole principle**: - Split each 64-bit fingerprint into **k + 1 blocks**. For k = 3 that is 4 blocks of 16 bits. - If two fingerprints differ in at most 3 bits, those bits touch at most 3 blocks, so **at least one block matches exactly**. - Build one exact-match index per block (or one sorted table per permutation that brings a block to the front). - For a new page, look up each of its blocks, then compute the full Hamming distance only on the candidates that share a block. The cost is storage: with 10 billion pages at 8 bytes per fingerprint, each table is about 80 GB, so four tables are about 320 GB before overhead. That is the price of turning a full scan into a few indexed lookups. ## MinHash: estimating set overlap **MinHash** answers a slightly different question: how much do two pages' **shingle sets** overlap, measured as **Jaccard similarity** (size of intersection divided by size of union)? - Apply many independent hash functions to every shingle and keep the minimum value for each function. - For any one hash function, the probability that two sets share the same minimum equals their Jaccard similarity, so the fraction of matching minimums estimates it. - **Banding** (a form of locality-sensitive hashing) groups the minimums into bands; pages sharing any whole band become candidates, which avoids pairwise comparison. | Technique | Catches | Size per page | Similarity measure | |---|---|---|---| | SHA-256 digest | exact copies only | 32 bytes | equal or not | | SimHash | small edits across the page | 8 bytes (64 bits) | Hamming distance | | MinHash | set overlap, including partial copies | many hash values (e.g. 100 or more) | estimated Jaccard | SimHash is favoured where compactness at billions of pages matters most; MinHash gives a more direct, tunable similarity estimate at a higher storage cost. ## Making it work in production - **Strip boilerplate first.** Navigation, footers and templates can dominate a short page, so two different articles on one site would look alike. Fingerprint the main content. - **Choose a canonical copy.** Keep one member of each cluster, for example the most important or shortest URL, and skip indexing the rest. - **Use it as a crawl signal.** A host that produces many URLs with the same fingerprint is likely generating variants or a trap; its priority or budget can be lowered, and a normalisation rule can be learned. - **Tune on labelled pairs.** Too loose a threshold merges genuinely different pages; too strict leaves duplicates in the index.

Why should a crawler strip navigation and boilerplate before computing SimHash?
On short pages the shared template can contribute most of the features, so two different articles from the same site would get fingerprints within the threshold and one would be dropped as a duplicate. Fingerprinting only the main content keeps the vote dominated by what makes each page distinct.
What should a crawler do once it finds a near-duplicate cluster?
Pick one canonical member, for example the most important or shortest URL, index that one, and skip or down-rank the rest. Record the cluster so later recrawls can skip copies cheaply. Count duplicates per host: a host generating many same-fingerprint URLs is a candidate for a learned normalisation rule, a lower priority, or a tighter crawl budget.
When would you choose MinHash over SimHash for near-duplicate detection?
When you need a direct, tunable estimate of set overlap, such as finding pages that copy part of another page, and can afford storing many hash values per page. SimHash is preferred when storage and lookup cost at billions of pages dominate, since it needs one 64-bit value per page.

saying these in an interview costs you the question

A SHA-256 of the page body is enough to catch near-duplicate pages.
SimHash behaves like a cryptographic hash, so similar pages get unrelated values.
Comparing each new fingerprint with every stored one is fine at web scale.
Near-duplicate detection should run on the raw HTML, templates included.
Two pages with identical SimHash values are guaranteed to be byte-identical.

How does a web crawler detect near-duplicate pages that an exact content hash misses?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Why exact hashing is not enough

SimHash: one 64-bit value per page

Searching billions of fingerprints

MinHash: estimating set overlap

Making it work in production

▾common follow-ups3 questions

▾red flags5 flags

Why exact hashing is not enough

SimHash: one 64-bit value per page

Searching billions of fingerprints

MinHash: estimating set overlap

Making it work in production

answer

go deeper