SimHash vs MinHash for Textual Near-Duplicates: Choosing the Right Primitive

Picking the wrong similarity primitive quietly degrades every near-duplicate result downstream: SimHash tuned for small edits misses documents that share most of their content but reorder it, while MinHash sized for set overlap wastes memory and misjudges tiny targeted edits. This decision sits at the foundation of near-duplicate detection, and getting it wrong shows up as clusters that do not match your intuitive notion of “these are the same document.” SimHash and MinHash both reduce a document to a compact fingerprint, but they measure different kinds of similarity, and the right choice depends on what “near-duplicate” means for your collection. This guide compares the two primitives on the axes that matter for eDiscovery and gives a decision procedure with a runnable implementation of each.

Diagnostic Log Signatures

The wrong-primitive symptom appears when clusters disagree with human judgment on a labeled sample. Capture it verbatim.

[INFO] Near-dup eval: primitive=simhash, hamming_threshold=3, 64-bit
[WARN] recall_on_reordered_pairs=0.41 (documents with same content, reordered sections)
[WARN] false_merge boilerplate cluster C-88: 30 docs share letterhead, differ in body
[INFO] Alt eval: primitive=minhash, num_perm=128, jaccard_threshold=0.8
[WARN] minhash recall_on_small_edits=0.62 (one-line change in a long contract)
[CRITICAL] Primitive mismatch: chosen fingerprint does not match the collection's similarity notion

Symptom checklist — two or more mean the primitive does not fit the data:

• Documents that a reviewer calls near-duplicates are not grouped, though their content clearly overlaps.
• Documents sharing only boilerplate (letterhead, signature blocks) are merged despite different substance.
• SimHash misses pairs whose content is reordered; MinHash misses pairs differing by a small localized edit.
• Tuning the threshold trades one error for the other without ever getting both right.
• The fingerprint size feels wrong for the scale — either too much memory or too little discriminating power.

How the Two Primitives Differ

MinHash estimates Jaccard similarity — the overlap of two documents’ sets of shingles — so it treats a document as an unordered bag of k-grams and asks what fraction of shingles they share. SimHash produces a single fingerprint whose Hamming distance approximates cosine similarity over weighted token features, so it is sensitive to the distribution of terms and their weights. The practical consequence: MinHash excels at set-overlap questions (how much of document A’s content also appears in B, regardless of order), while SimHash excels at detecting small perturbations of a weighted feature vector (a mostly-identical document with a few changed terms).

Neither is universally better; they answer different questions. In eDiscovery, MinHash is the more common default because “how much content do these share” matches how reviewers think about drafts, format-conversions, and quoted email — but SimHash’s tiny fingerprint and sensitivity to small edits make it attractive for very large collections of highly-templated documents where memory dominates.

Decision Procedure

Choose by the similarity notion your collection needs, then validate on labeled pairs.

1. Characterize your near-duplicates. If the pairs you must catch differ by reordering, insertion, or partial overlap (quoted replies, assembled documents), favor MinHash’s set-overlap model. If they differ by small localized edits to otherwise identical content and memory is tight, favor SimHash.
2. Weigh features to neutralize boilerplate. For SimHash especially, weight tokens (TF-IDF or a stoplist for letterhead/signatures) so shared boilerplate does not dominate the fingerprint and cause false merges.
3. Validate both on a labeled sample. Run each primitive over the same labeled near-dup and non-dup pairs and compare recall and precision at a tuned threshold before committing.
4. Match fingerprint size to scale. At extreme scale where signature memory is the bottleneck, SimHash’s single word per document may decide it; where discrimination and reordering-robustness matter more, MinHash’s larger signature earns its cost.

The two fingerprinting paths below show where they converge (a candidate-generation step) and where they differ.

Both primitives, side by side

The module implements a 64-bit SimHash with Hamming distance and reuses a MinHash Jaccard estimate, so the two can be evaluated on the same pairs. It compiles and runs on the standard library.

import hashlib
import re
from collections import Counter
from typing import Dict, List, Sequence


def tokens(text: str) -> List[str]:
    return re.sub(r"\s+", " ", text.lower()).strip().split(" ")


def _token_hash(token: str) -> int:
    return int.from_bytes(hashlib.blake2b(token.encode(), digest_size=8).digest(), "big")


def simhash(text: str, weights: Dict[str, float] | None = None, bits: int = 64) -> int:
    """Weighted 64-bit SimHash: each token votes on every bit by its weight,
    and the sign of each bit's vote total forms the fingerprint."""
    vote = [0.0] * bits
    counts = Counter(tokens(text))
    if not counts:
        raise ValueError("cannot fingerprint empty text")
    for token, tf in counts.items():
        w = (weights.get(token, 1.0) if weights else 1.0) * tf
        h = _token_hash(token)
        for i in range(bits):
            vote[i] += w if (h >> i) & 1 else -w
    fp = 0
    for i in range(bits):
        if vote[i] > 0:
            fp |= (1 << i)
    return fp


def hamming(a: int, b: int) -> int:
    """Number of differing bits — the SimHash distance."""
    return bin(a ^ b).count("1")


def simhash_similar(a: int, b: int, max_hamming: int = 3) -> bool:
    """Two documents are near-duplicates if their fingerprints differ in at
    most max_hamming bits (a small localized edit flips few bits)."""
    return hamming(a, b) <= max_hamming


def choose_primitive(reordered_fraction: float, small_edit_fraction: float,
                     memory_constrained: bool) -> str:
    """Heuristic selector: favor MinHash for reordering/partial overlap,
    SimHash for small edits under tight memory."""
    if reordered_fraction >= 0.3:
        return "minhash"          # set-overlap robustness to reordering
    if small_edit_fraction >= 0.5 and memory_constrained:
        return "simhash"          # tiny fingerprint, edit sensitivity
    return "minhash"              # the eDiscovery default

Verification Checklist

Confirm the primitive fits before committing a collection to it:

• The near-duplicate pairs you must catch are characterized (reordering/partial-overlap vs small localized edits).
• Token weighting neutralizes shared boilerplate so it does not drive false merges — critical for SimHash.
• Both primitives were evaluated on the same labeled pair set, and the chosen one meets recall and precision targets.
• The fingerprint size is justified by the collection scale and memory budget.
• The chosen primitive, its parameters, and the evaluation results are version-controlled and logged.

Conclusion

SimHash and MinHash are not interchangeable — they measure different similarities, and the right choice follows from what “near-duplicate” means for your collection. MinHash’s set-overlap model matches how reviewers think about drafts, format-conversions, and quoted text, and it is the eDiscovery default; SimHash’s tiny fingerprint and edit sensitivity make it compelling for massive, highly-templated collections where memory dominates and token weighting can tame boilerplate. Characterize your near-duplicate pairs, weight features to neutralize shared content, validate both primitives on the same labeled sample, and log the decision. Chosen this way, the fingerprint matches your similarity notion, and the clusters downstream finally agree with human judgment.

Frequently Asked Questions

Which is the better default for eDiscovery, SimHash or MinHash?

MinHash with LSH is the more common eDiscovery default, because Jaccard set overlap closely matches how reviewers think about near-duplicates — drafts, format conversions, and quoted email all share large fractions of content regardless of order, which is exactly what set overlap captures. SimHash becomes attractive at extreme scale, or for highly-templated document populations, where its single-word fingerprint saves substantial memory and its edit sensitivity is a good fit — provided you weight tokens to keep boilerplate from dominating.

Why does SimHash over-merge documents that only share boilerplate?

Because an unweighted SimHash lets every token vote equally on the fingerprint, so shared letterhead, signature blocks, and legal disclaimers push two documents’ fingerprints close together even when their substance differs. Weighting tokens — with TF-IDF or a stoplist that down-weights common boilerplate — restores the fingerprint’s sensitivity to the substantive content, which is why feature weighting is more important for SimHash than for MinHash.

Can I use both primitives together?

Yes. A common pattern is a cheap first pass with SimHash to bucket obvious candidates, followed by a MinHash/Jaccard confirmation on the survivors for precision, or vice versa. The cost is maintaining two fingerprinting paths and two sets of parameters, so it is worth it mainly at scales where one primitive alone cannot hit both the recall and precision targets. For most collections, one well-chosen and well-tuned primitive is sufficient and simpler to defend.

Related

• Near-Duplicate Detection — the subsystem this primitive plugs into.
• Tuning MinHash LSH Bands — tuning the MinHash candidate generation.
• Similarity Threshold Configuration — governing the threshold either primitive applies.
• Hash-Based Deduplication Strategies — the exact-match stage upstream.

For background, see Charikar’s SimHash paper and Stanford’s Mining of Massive Datasets on MinHash and LSH.

Up one level: Near-Duplicate Detection — the subsystem that clusters similar documents at scale.