Skip to content
AfluidityAlgorithm Atlas
SearchingAll categories
CoreConcept & Pseudocode EntryAI Reviewed (ai-reviewed)

SimHash

Compresses a weighted feature or token set into a fixed 64-bit locality-sensitive fingerprint whose Hamming distance approximates cosine similarity for fast near-duplicate document detection.

Explore relationshipsOpen 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Searching
Difficulty
Intermediate
Family
Locality-Sensitive Hashing & Similarity
Tier
Core
Status
Reviewed
Review
AI Reviewed
Sources
2
Formulas
1
Relationships
2
Code example
Not ready
Visualization
Ready
Aliases
Charikar SimHash, Near-Duplicate Document Fingerprinting, Cosine Random Hyperplane LSH

Overview

Invented by Moses Charikar and popularized by Google for web-scale crawler deduplication, SimHash hashes each document token/shingle to a b-bit (typically 64-bit) value, adds +weight to accumulator V[i] when bit i is 1 and -weight when bit i is 0, and sets fingerprint bit i to 1 iff V[i] > 0. Two documents that differ in only a few words produce 64-bit fingerprints within a small Hamming distance (e.g. <= 3 bits).

Core Concepts

random hyperplane projectionsigned bit accumulator vectorHamming distancepigeonhole block partitioning

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(b * |tokens|) per document, O(1) bitwise XOR+popcount comparison

Average

O(b * |tokens|)

Worst

O(b * |tokens|)

Space

O(b) per document (8 bytes for 64-bit fingerprint)

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for SimHash across input scales.

Input Scale N:
JIT-compiled JS/TS (~350M primitive ops/sec)
Est. Average TimeO(b * |tokens|)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Worst-Case TimeO(b * |tokens|)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Working MemoryO(b) per document (8 bytes for 64-bit fingerprint)

1.53 MB

Standard Heap FitN=100,000

When to Use

  • Use it for web-scale near-duplicate document, article, and webpage detection across billions of pages using 8-byte fingerprints and bitwise XOR + POPCNT.
  • Choose it when token weights (such as TF-IDF) and cosine similarity matter more than unweighted set Jaccard similarity.
  • Combine it with pigeonhole block partitioning (splitting a 64-bit hash into 4 blocks of 16 bits) to find all fingerprints within Hamming distance k = 3 in O(1) table lookups.

When Not to Use

  • Avoid SimHash when unweighted set containment or Jaccard similarity over variable-length sets is required; use MinHash instead.
  • Do not use SimHash for cryptographic integrity verification or tamper detection; use SHA-256 or BLAKE3 instead.

What It Does

  • Computes a compact 64-bit locality-sensitive hash where similar documents share nearby bit patterns
  • Detects near-duplicate web pages, articles, or text documents by checking if HammingDistance(f1, f2) <= k

Use Cases

  • Detecting near-duplicate webpages and syndicated news articles within 3 Hamming bits in web search crawlers
  • Clustering boilerplate emails, spam campaigns, and plagiarized text passages at multi-billion document scale
  • Deduplicating similar source-code files and log templates using 64-bit locality-sensitive fingerprints

Inputs

  • Document tokens/shingles with weights (w_t) and fingerprint bit width b (e.g., 64)

Outputs

  • b-bit SimHash fingerprint and pairwise Hamming distance

Key Formulas (1)

Random Hyperplane Collision Probability

P[biti(u) = biti(v)] = 1 − arccos(u . v / (||u|| ||v||)) / π
P[bit_i(u) == bit_i(v)] = 1 - arccos(u . v / (||u|| ||v||)) / pi

Expected fraction of matching SimHash bits is linear in the angle between the document vectors.

Pseudocode

  1. 1.Initialize accumulator array V[0..63] = 0
  2. 2.For each token (or shingle) t with weight w in the document:
  3. 3. Compute 64-bit hash h = hash64(t)
  4. 4. For bit index i from 0 to 63:
  5. 5. If ((h >> i) & 1) == 1: V[i] += w else: V[i] -= w
  6. 6.Initialize 64-bit fingerprint F = 0
  7. 7.For i from 0 to 63: if V[i] > 0, set bit i of F to 1
  8. 8.Compare two fingerprints F1, F2 via popcount(F1 XOR F2) <= k

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

  1. Initialize accumulator array V[0..63] = 0
  2. For each token (or shingle) t with weight w in the document:
  3. Compute 64-bit hash h = hash64(t)
  4. For bit index i from 0 to 63:
  5. If ((h >> i) & 1) == 1: V[i] += w else: V[i] -= w
  6. Initialize 64-bit fingerprint F = 0
  7. For i from 0 to 63: if V[i] > 0, set bit i of F to 1
  8. Compare two fingerprints F1, F2 via popcount(F1 XOR F2) <= k

Canonical Example

Input
Doc A = 'the cat sat on the mat', Doc B = 'the cat sat on a mat'
Output
HammingDistance(SimHash(A), SimHash(B)) = 2 bits (out of 64) <= threshold 3 -> near-duplicate
Explanation
Because 5 of 6 tokens match, the signed bit accumulators V[0..63] have the same sign in 62 of 64 positions.

Implementation Notes

  • To query Hamming distance <= 3 in 64-bit fingerprints in O(1) index lookups, split 64 bits into 4 blocks of 16 bits; any pair with <= 3 bit flips must match identically in at least one 16-bit block.

Common Pitfalls

  • Hashing individual single words instead of 3-word shingles or character n-grams on short texts, which loses phrase order.
  • Scanning all N fingerprints linearly for Hamming distance <= k instead of splitting the 64-bit fingerprint into k + 1 blocks via the pigeonhole principle for exact block-index lookup.

Interactive Mechanism Walkthrough & State Debugger

Indexed Interval & Boundary Probe
Target key: 41low=5, mid=4, high=9
4[0]
9[1]
15[2]
22[3]
27[4]
34[5]
41[6]
49[7]
58[8]
63[9]
target41
window [low..high][5 .. 9]
probe mididx 4 (val=27)
comparison27 < 41 (Go Right)
Step 1 of 8: Initialize accumulator array V[0..63] = 0

Sources (2)

What each reference supports for this entry.

Charikar (2002) — Similarity Estimation Techniques from Rounding Algorithms (STOC '02)

Paper

Introduces random hyperplane LSH (SimHash) for cosine similarity.

Open source

Manku, Jain & Das Sarma (2007) — Detecting Near-Duplicates for Web Crawling (WWW '07)

Paper

Google's 64-bit SimHash + pigeonhole table design for multi-billion-page deduplication.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Alternative toMinHash

Pattern Matching · Core

Approximates weighted cosine similarity via bit-sign voting rather than unweighted Jaccard set similarity.

Compare with this
SpecializesLocality-Sensitive Hashing

Pattern Matching · Core

Specializes random-hyperplane LSH into a 64-bit document fingerprint queried by Hamming distance.

Compare with this

Relationships

View full relationship page
SpecializesLocality-Sensitive Hashing

Specializes random-hyperplane LSH into a 64-bit document fingerprint queried by Hamming distance.

Alternative toMinHash

Approximates weighted cosine similarity via bit-sign voting rather than unweighted Jaccard set similarity.

Related Algorithms

Locality-Sensitive HashingMinHashCosine SimilarityBloom Filter

Tags

HashingLocality Sensitive HashingDeduplicationInformation Retrieval