Near-Duplicate Detection with Simhash
What you'll learn: How to efficiently identify web pages with nearly identical content using locality-sensitive hashing.
While exact duplicate detection (using content fingerprinting with hashing or Bloom filters for URL seen checking) catches identical pages, many web pages are almost the same—think mirrors, spam variations, or boilerplate-heavy sites. Simhash is a locality-sensitive hashing technique that produces similar fingerprints for similar documents.
How Simhash Works
Unlike cryptographic hashes where one character change completely alters the output, Simhash generates a fixed-length fingerprint (typically 64 or 128 bits) where similar documents produce similar hashes. The key property: the Hamming distance (number of differing bits) between two Simhash values correlates with content similarity.
The intuition: Imagine summarizing a document with weighted features (word frequencies, n-grams). Simhash turns these features into a compact binary signature. Documents with overlapping features end up with fingerprints that differ in only a few bit positions.
In a Crawler Context
After extracting and normalizing content:
- Compute the Simhash fingerprint for each page
- Store fingerprints in a database or distributed storage
- For new pages, compute their Simhash and compare against existing ones
- If Hamming distance ≤ threshold (e.g., 3 bits difference out of 64), consider it a near-duplicate
- Skip crawling or index only one canonical version
Challenge at scale: Comparing every new fingerprint against billions of stored ones is impractical. Solutions include using banding techniques (splitting fingerprints into segments) or LSH tables to quickly find candidates with low Hamming distance.
Key Takeaway: Simhash enables efficient near-duplicate detection by transforming content into compact binary signatures where similarity in content translates to proximity in hash space, allowing crawlers to avoid wasting resources on redundant pages.