Near-Duplicate Detection at Web Scale: SimHash, MinHash & Locality-Sensitive Hashing

Across the public World Wide Web, an estimated $30%$ to $40%$ of all indexed content consists of duplicate or near-duplicate documents. These duplicate pages originate from syndicated news wire articles, mirrored e-commerce product listings, automated scrapers, session tracking ID URL variants, and slight typographical differences (such as different copyright years in footers or localized header banners). While exact duplicates can be detected instantly using cryptographic hash functions (such as SHA-256 or MD5), exact hashes change completely if even a single comma or timestamp changes. Web-scale search engines require near-duplicate detection algorithms powered by Charikar's SimHash, MinHash with Jaccard similarity, and Locality-Sensitive Hashing (LSH).

1. Exact vs. Syntactic vs. Semantic Deduplication

Evaluating the boundaries between deduplication technologies across the web search pipeline:

2. Charikar's SimHash Algorithm: 64-Bit Dimensionality Reduction

Developed by Moses Charikar and famously deployed by Google for web-scale deduplication, SimHash maps an arbitrary-length document into a single 64-bit integer with a remarkable property: the Hamming distance (number of differing bits) between two SimHash fingerprints is directly proportional to their textual difference.

• Algorithm Execution Steps:
  1. Initialize a 64-dimensional accumulator vector $V$ with zeros: $V = [0, 0, dots, 0]$.
  2. Extract tokens (or word shingles) from document $D$ and assign each an integer weight $w_i$ (e.g., term frequency or TF-IDF).
  3. For each token, compute its standard 64-bit hash (using MurmurHash3 or FNV-1a).
  4. For each of the 64 bit positions: if the $j$-th bit of the token hash is $1$, add $w_i$ to $V[j]$; if the $j$-th bit is $0$, subtract $w_i$ from $V[j]$.
  5. After summing all tokens, construct the final 64-bit SimHash fingerprint: if $V[j] > 0$, set bit $j$ to $1$; otherwise set bit $j$ to $0$.
• Hamming Distance Threshold: In practice, two web documents are considered near-duplicates if their 64-bit SimHash values differ by 3 bits or fewer ($k le 3$).

3. Sub-Linear SimHash Table Lookups (The Pigeonhole Principle)

Even with 64-bit fingerprints, comparing a new document against 1 billion stored hashes would require 1 billion XOR operations. To achieve sub-millisecond retrieval, engineers exploit the Pigeonhole Principle:

• Split the 64-bit fingerprint into 4 equal 16-bit blocks: $B_1, B_2, B_3, B_4$.
• If two documents differ by at most $k = 3$ bits across 64 bits, then by the pigeonhole principle, at least one of the four 16-bit blocks must be 100% identical.
• Maintain 4 separate hash tables, each indexed by a different 16-bit block permutation. Querying requires checking only the candidates that share an exact 16-bit block match, reducing candidate evaluations from 1 billion to a few hundred.

4. MinHash & Locality-Sensitive Hashing (LSH)

While SimHash excels at comparing documents of similar length, MinHash (Broder) measures the Jaccard similarity between two sets of document $n$-grams (shingles): $J(A, B) = rac{|A cap B|}{|A cup B|}$.

• MinHash Principle: By applying $m$ random hash functions to the set of shingles, the probability that two documents share the minimum hash value under a hash function $h_i$ is mathematically identical to their Jaccard similarity: $P(min(h_i(A)) = min(h_i(B))) = J(A, B)$.
• LSH Banding: The $m$ MinHash values are partitioned into $b$ bands containing $r$ rows each ($m = b cdot r$). Documents that hash to the identical bucket within any single band become candidate pairs. This transforms the candidate search probability into an S-curve: pairs with high similarity are guaranteed to be identified, while dissimilar documents are rejected with zero overhead.

5. Production Implementation: SimHash Generator & Hamming Distance

The following TypeScript blueprint demonstrates an enterprise 64-bit SimHash generator with token weighting and bitwise Hamming distance calculation:

export class SimHash {
  // Generate 64-bit BigInt SimHash fingerprint from weighted token stream
  static generate(tokens: string[]): bigint {
    const v = new Array(64).fill(0);
    const tokenWeights = new Map<string, number>();

    // Calculate term frequencies as weights
    for (const t of tokens) {
      tokenWeights.set(t, (tokenWeights.get(t) || 0) + 1);
    }

    for (const [token, weight] of tokenWeights.entries()) {
      const hash = this.fnv1a64(token);

      for (let i = 0; i < 64; i++) {
        const bit = (hash >> BigInt(i)) & 1n;
        v[i] += bit === 1n ? weight : -weight;
      }
    }

    let fingerprint = 0n;
    for (let i = 0; i < 64; i++) {
      if (v[i] > 0) {
        fingerprint |= 1n << BigInt(i);
      }
    }

    return fingerprint;
  }

  // Calculate bitwise Hamming distance between two 64-bit fingerprints
  static hammingDistance(a: bigint, b: bigint): number {
    let xor = a ^ b;
    let distance = 0;

    while (xor > 0n) {
      distance += Number(xor & 1n);
      xor >>= 1n;
    }

    return distance;
  }

  // 64-bit FNV-1a string hashing implementation
  private static fnv1a64(str: string): bigint {
    let hash = 0xcbf29ce484222325n;
    const prime = 0x100000001b3n;

    for (let i = 0; i < str.length; i++) {
      hash ^= BigInt(str.charCodeAt(i));
      hash = (hash * prime) & 0xffffffffffffffffn;
    }

    return hash;
  }
}