Syntactic clustering of the Web

Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, Geoffrey ZweigComputer Networks and ISDN Systems 1997 · DOI

This classic 1997 paper from Digital Equipment Corporation’s Systems Research Center introduces a scalable method for finding "roughly the same" documents across the burgeoning World Wide Web. By representing documents as sets of "shingles" (n-grams) and using mathematical "sketches" to estimate similarity, the authors demonstrated the first large-scale clustering of 30 million web pages to combat duplication and URL instability.

TL;DR

The authors developed an efficient, "shingle"-based sketching technique to determine the syntactic similarity of web pages at scale. By applying this to 30 million documents, they created a system that can identify near-duplicates, track moved content ("Lost and Found"), and group search results, all while avoiding the impossible $O(N^2)$ cost of pairwise comparisons.

What Problem Does This Paper Address?

In the mid-90s, the Web was experiencing exponential growth, leading to two major headaches:

  1. Proliferation of Duplicates: The same content (FAQs, manuals, legal docs) appeared in multiple places with minor variations like different headers, footers, or formatting.
  2. URL Instability: Links broke constantly as pages moved or servers were renamed.

Traditional search engines struggled with this "noise," often returning ten versions of the same document in a top-ten list. The authors sought a way to mathematically define and efficiently compute "syntactic similarity"—the idea that two documents are nearly identical in text, even if their underlying HTML or metadata differs.

Methods

The core of the approach is a technique called shingling:

  • Shingles: A document is treated as a sequence of tokens. A $w$-shingle is a contiguous subsequence of $w$ tokens. For example, a 4-shingling of "(a, rose, is, a, rose)" produces the set {(a, rose, is, a), (rose, is, a, rose)}.
  • Resemblance and Containment: Similarity is defined by the Jaccard overlap of these shingle sets. "Resemblance" measures how much two docs are the same; "Containment" measures if one doc is a subset of another.
  • Sketches: Since storing every shingle for every web page is impossible, the authors used "sketches"—a small, fixed-size fingerprint of the shingle set. They used a "modulus" method (keeping shingles where the hash value is $0 \pmod m$) or a "min-hash" approach (keeping the smallest $s$ elements of a random permutation).
  • Super Shingles: To speed up clustering even further, they introduced "super shingles"—sketches of the sketches. If two documents share even one super shingle, they are almost certainly highly similar.
  • The Pipeline: To handle 30 million docs, they used a four-phase "divide, sort, merge" algorithm that minimized random disk access, relying instead on linear passes and union-find algorithms to build clusters.

Datasets

The authors evaluated their system using a massive (for the time) dataset:

  • AltaVista Crawl: 30,000,000 HTML and text documents retrieved by the AltaVista spider in April 1996.
  • Scale: The total input data was 150 GB.
  • Parameters: They used 10-word shingles and 40-bit Rabin fingerprints, keeping 1 in every 25 shingles.

Key Insights and Ideas

  • Syntactic vs. Semantic: The paper focuses purely on syntactic similarity (the words used) rather than semantic similarity (the meaning). This is much easier to compute at scale and highly effective for finding duplicates.
  • Ignoring "Common" Shingles: They discovered that shingles appearing in more than 1,000 documents were almost always mechanically generated (e.g., HTML comments, navigation bars). Ignoring these "stop-shingles" significantly improved both performance and clustering quality.
  • The Power of Sketches: By using sketches, you can estimate the similarity of two documents without ever needing to see the original files again. This allows for "on-the-fly" resemblance checks against a massive index.
  • Clustering as a Service: The authors envisioned the "Lost and Found" service: if a URL dies, the system looks up the document's cluster and directs the user to a "syntactically similar" version at a different URL.

Key Results

The system was remarkably efficient and effective:

  • Clustering Performance: The entire process (sketching to cluster formation) took roughly 10.5 CPU-days on the 30M document set.
  • Cluster Statistics: Using a 50% resemblance threshold, they found 3.6 million clusters containing 12.3 million documents.
  • Duplicate Density: Of those clusters, 2.1 million contained only identical documents (5.3 million docs total), while 1.5 million clusters contained a mix of exact and near-duplicates (7 million docs total).

Limitations and Future Work

  • Short Documents: The shingling method is less accurate for very short documents, as they produce too few shingles for a reliable sketch.
  • Super Shingle Trade-offs: While super shingles are incredibly fast, they cannot detect "containment" (e.g., a short article inside a larger digest) because the extra material in the larger doc changes the sequence of shingles.
  • Security: The authors note that their static sketching policy is vulnerable to adversarial manipulation, making it less suitable for high-stakes plagiarism or intellectual property enforcement compared to more secure (but slower) sampling methods.

This summary is based on the SRC Technical Note 1997-015.

The paper was produced by Digital Equipment Corporation's Systems Research Center.

Summary updated

BibTeX
@inproceedings{broder1997syntactic,
  author = {Andrei Z. Broder and Steven C. Glassman and Mark S. Manasse and Geoffrey Zweig},
  title = {{Syntactic clustering of the Web}},
  booktitle = {Computer Networks and ISDN Systems},
  year = {1997},
  doi = {10.1016/s0169-7552(97)00031-7},
}
On the resemblance and containment of documentsProceedings. Compression and Complexity of Sequences 1997 (cat. No.97tb100171)
On the evolution of clusters of near-duplicate Web pagesProceedings of the Ieee/leos 3rd International Conference on Numerical Simulation of Semiconductor Optoelectronic Devices (ieee Cat. No.03ex726)
Finding near-duplicate web pages: a large-scale evaluation of algorithmsSIGIR · 2006
b-Bit minwise hashingarXiv · 2009
LSHBloom: Memory-efficient, Extreme-scale Document DeduplicationarXiv · 2024
A Review for Weighted MinHash Algorithms.arXiv · 2018
Figure