On the resemblance and containment of documents

A.z. BroderProceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171) · DOI

TL;DR

This seminal paper introduces a scalable way to identify "roughly the same" or "roughly contained" documents across massive datasets like the World Wide Web. By converting documents into sets of "shingles" and using a technique now known as Min-Hashing, the author demonstrates how to estimate document similarity using tiny, fixed-size "sketches" rather than comparing full texts.

What Problem Does This Paper Address?

In the late 90s, the World Wide Web was exploding, leading to a massive proliferation of identical or near-identical documents (mirrors, legal disclaimers, slightly edited versions of the same article).

Traditional string distance metrics like Levenshtein (edit distance) or Hamming distance are computationally expensive—they require pairwise comparisons of entire documents. For a collection of millions of documents, this is mathematically impossible to do in a reasonable timeframe. The challenge was to find a mathematical framework that captures the informal notion of "resemblance" while allowing for a sampling mechanism that can be computed independently for each document.

Methods

The paper proposes a two-step approach: Shingling and Sketching.

  1. Shingling: A document is treated as a sequence of tokens (words or characters). A "$w$-shingle" is a contiguous subsequence of $w$ tokens. By representing a document as a set (or multiset) of these shingles, the problem of document similarity is transformed into a set intersection problem.
  2. Resemblance ($r$): Defined as the size of the intersection of two shingle sets divided by the size of their union (the Jaccard similarity).
  3. Containment ($c$): Defined as the size of the intersection divided by the size of the smaller document's set.
  4. Sketching (Min-Hashing): To avoid storing thousands of shingles per document, the author uses a random permutation of the shingle space. By keeping only the $s$ smallest elements (the "sketch") of the permuted set, one can produce an unbiased estimate of the resemblance.
  5. Crucially, these sketches are small and fixed-size (e.g., 100–200 samples), meaning you can compare two 100MB files just as quickly as two 10KB files.
  6. Implementation: The paper suggests using Rabin fingerprints to hash shingles efficiently. Rabin fingerprints are particularly useful here because they can be computed using a "sliding window" approach, making the shingling process very fast.

Datasets

The authors tested their theory on a massive (for 1997) real-world dataset:

  • AltaVista Web Crawl: A collection of over 30,000,000 documents totaling over 150 Gbytes of data.
  • This was a landmark evaluation, proving the algorithm could handle the scale of the entire public web at the time.

Key Insights and Ideas

  • Independence is Key: Sketches can be computed for each document independently. You don't need to see Document B to prepare the sketch for Document A. This allows for massive parallelization.
  • The Metric Property: The author notes that $d(A, B) = 1 - r(A, B)$ is a mathematical metric (it obeys the triangle inequality). This is a "hidden gem" because it allows researchers to use standard clustering algorithms that rely on metric spaces.
  • Sensitivity Tuning: The choice of shingle size $w$ acts as a "knob." A small $w$ is sensitive to small changes; a large $w$ is more robust to permutations but might miss subtle similarities.
  • Fixed-Size vs. Variable-Size: While resemblance can be estimated with a fixed-size sketch, the paper notes that estimating containment accurately usually requires a sketch proportional to the document size, though they provide a "modulus" trick to finesses this.

Key Results

  • Efficiency: The clustering of 30 million documents was successful. They found 3.6 million clusters containing 12.3 million documents.
  • Duplicate Discovery: Out of those clusters, 2.1 million contained only identical documents (5.3 million total), while 1.5 million clusters contained a mix of exact and near-duplicates (7 million total).
  • Accuracy: The paper provides a probabilistic bound: with a sample size of 100–200, the estimate is highly reliable. For example, it is extremely unlikely (less than 0.1% chance) that a pair of documents with less than 50% resemblance would be mistakenly estimated as having more than 90% resemblance.

Limitations and Future Work

  • Short Documents: The estimation of containment for very short documents within much larger ones is "error-prone due to the paucity of samples."
  • Clustering Bottlenecks: While comparing two sketches is $O(s)$, clustering millions of sketches still requires clever algorithmic work (like the "greedy clustering" mentioned) to avoid $O(N^2)$ comparisons.
  • Storage Trade-offs: There is a constant trade-off between the fingerprint size (in bits) and the probability of a hash collision, which could degrade the estimate.

This paper laid the groundwork for modern "Locality Sensitive Hashing" (LSH) and remains a foundational text for anyone working on search engines, data deduplication, or large-scale data mining.

Summary updated

BibTeX
@inproceedings{broderresemblance,
  author = {A.Z. Broder},
  title = {{On the resemblance and containment of documents}},
  booktitle = {Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171)},
  doi = {10.1109/sequen.1997.666900},
}
Figure