Why use MinHash and LSH instead of comparing documents directly?

Direct comparison is quadratic and impossible at scale — a million documents is around 500 billion pairs. MinHash reduces each document to a fixed-length signature estimating Jaccard similarity, bounding memory, and LSH buckets signatures so only plausibly-similar documents are compared, avoiding the all-pairs blowup. Together they make detection near-linear at the cost of a small, controllable estimation error.

Near-Duplicate Detection: MinHash, LSH, and Defensible Similarity Clustering

Exact-match hashing collapses byte-identical files, but it is blind to the documents that matter most to a reviewer: the fifth draft of a contract, the same memo saved as DOCX and PDF, an email quoted inside a later reply. These are near duplicates — textually almost the same, cryptographically completely different — and grouping them is what lets a reviewer make one decision for a family of revisions instead of twenty. Inside the Deduplication & Family Grouping pipeline, near-duplicate detection is the subsystem that measures textual similarity at scale and clusters documents above a defensible threshold. The engineering challenge is that comparing every document to every other is quadratic and impossible at ESI volumes; the solution is a probabilistic pipeline — shingling, MinHash signatures, and locality-sensitive hashing — that finds the similar pairs without the quadratic blowup. This guide builds it.

Near-Duplicate Subsystem Flow

Similarity detection is a funnel: text is normalized into shingles, each document is reduced to a compact MinHash signature that estimates Jaccard similarity, LSH buckets candidate pairs so only plausibly-similar documents are compared, and the survivors are clustered above a version-controlled threshold with every decision logged.

Memory & Resource Constraints

The naive near-duplicate approach compares every document to every other and computes exact Jaccard similarity on full token sets. Both are fatal at scale: the all-pairs comparison is $O(n^2)$ — a million documents is 500 billion comparisons — and holding every document’s full shingle set in memory is unbounded. Near-duplicate detection is only tractable because it replaces both with approximations that trade a controlled amount of accuracy for orders-of-magnitude less work.

The MinHash signature is the memory fix: instead of a document’s full shingle set, it stores a fixed number of minimum hash values (say 128) that estimate the set’s Jaccard similarity with any other. Every document, regardless of length, reduces to a constant-size signature, so signature storage is linear and bounded. LSH is the comparison fix: it hashes signatures into buckets such that similar signatures collide, so only documents that share a bucket are ever compared. Together they turn a quadratic, unbounded problem into a linear-memory, near-linear-time pipeline that runs on the same worker model as the rest of the hash-based deduplication strategies.

MinHash and LSH Algorithm Deep-Dive

The foundation is Jaccard similarity: for two shingle sets $A$ and $B$ ,

J(A, B) = \frac{|A \cap B|}{|A \cup B|}.

MinHash exploits a key property: if $h$ is a random hash function, the probability that the minimum hash over $A$ equals the minimum over $B$ is exactly the Jaccard similarity, $\Pr[\min h(A) = \min h(B)] = J(A, B)$ . Using $k$ independent hash functions, the fraction of signature positions where two documents agree is an unbiased estimate of $J$ , with error shrinking as $1/\sqrt{k}$ . A 128-value signature estimates Jaccard to within roughly $\pm 0.09$ , enough to separate near-duplicates from unrelated documents.

LSH then tunes the recall/precision trade-off through a banding scheme. The $k$ -value signature is split into $b$ bands of $r$ rows each ( $k = b \times r$ ), and two documents become candidates if they match in any band. The probability that a pair with true similarity $s$ becomes a candidate is $1 - (1 - s^r)^b$ , an S-curve whose steepness and threshold are set by $b$ and $r$ . Choosing the band count to place the S-curve’s midpoint at the desired similarity threshold is the core tuning decision, worked through in tuning MinHash LSH bands; the choice between MinHash and the alternative SimHash approach is covered in SimHash vs MinHash for textual near-dupes.

Resilience & Failure Routing

Near-duplicate clustering fails toward review, never toward silent culling. Because the similarity estimate is probabilistic, a pair near the threshold is genuinely uncertain, so the subsystem uses tiered gates: documents whose estimated similarity is comfortably above the threshold cluster automatically, documents in a band around the threshold are flagged for manual confirmation, and documents below it route to independent review. No document is ever excluded from review on a probabilistic score alone — the same defensibility principle the similarity threshold configuration layer enforces.

Two failure modes get explicit guards. Signature instability — a document whose extracted text is too short to shingle meaningfully — is detected and routed to exact-match handling rather than assigned an unreliable signature. Threshold drift — an ungoverned change to the similarity cutoff — is prevented by version-controlling the threshold and banding parameters and logging every clustering decision with the parameters in force, so a near-duplicate group can always be explained by the exact configuration that produced it. This makes the near-duplicate layer reproducible: the same collection under the same parameters yields the same clusters.

Production Python Implementation

The module shingles normalized text, computes MinHash signatures, buckets by LSH banding, and clusters candidates above a threshold with estimated similarity. It compiles and runs on the standard library (using hashlib for stable hashing).

python

import hashlib
import logging
import re
from dataclasses import dataclass, field
from typing import Dict, List, Sequence, Set, Tuple

logger = logging.getLogger("ediscovery.neardup")


def shingles(text: str, k: int = 5) -> Set[str]:
    """Overlapping k-word shingles over normalized text."""
    tokens = re.sub(r"\s+", " ", text.lower()).strip().split(" ")
    if len(tokens) < k:
        return {" ".join(tokens)} if tokens != [""] else set()
    return {" ".join(tokens[i:i + k]) for i in range(len(tokens) - k + 1)}


def _hash(value: str, seed: int) -> int:
    h = hashlib.blake2b(f"{seed}:{value}".encode(), digest_size=8)
    return int.from_bytes(h.digest(), "big")


def minhash_signature(shingle_set: Set[str], num_perm: int = 128) -> List[int]:
    """A fixed-length signature: the minimum hash under each of num_perm seeds.
    Length is constant regardless of document size, so storage is bounded."""
    if not shingle_set:
        raise ValueError("cannot sign an empty shingle set")
    return [min(_hash(s, seed) for s in shingle_set) for seed in range(num_perm)]


def estimate_jaccard(sig_a: Sequence[int], sig_b: Sequence[int]) -> float:
    """Fraction of agreeing positions — an unbiased Jaccard estimate."""
    if len(sig_a) != len(sig_b):
        raise ValueError("signatures must be equal length")
    agree = sum(1 for a, b in zip(sig_a, sig_b) if a == b)
    return agree / len(sig_a)


def lsh_buckets(signatures: Dict[str, List[int]], bands: int
                ) -> Dict[Tuple[int, int], List[str]]:
    """Split each signature into `bands` bands; documents sharing a band-hash
    become candidates. Only these pairs are ever compared."""
    buckets: Dict[Tuple[int, int], List[str]] = {}
    for doc_id, sig in signatures.items():
        if len(sig) % bands != 0:
            raise ValueError("signature length must be divisible by band count")
        rows = len(sig) // bands
        for b in range(bands):
            band = tuple(sig[b * rows:(b + 1) * rows])
            key = (b, hash(band))
            buckets.setdefault(key, []).append(doc_id)
    return buckets


def cluster_near_duplicates(signatures: Dict[str, List[int]], bands: int,
                            threshold: float) -> List[Set[str]]:
    """Cluster documents whose estimated similarity meets the threshold,
    comparing only LSH candidate pairs."""
    buckets = lsh_buckets(signatures, bands)
    parent: Dict[str, str] = {d: d for d in signatures}

    def find(x: str) -> str:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a: str, b: str) -> None:
        parent[find(a)] = find(b)

    seen_pairs: Set[Tuple[str, str]] = set()
    for members in buckets.values():
        for i in range(len(members)):
            for j in range(i + 1, len(members)):
                pair = tuple(sorted((members[i], members[j])))
                if pair in seen_pairs:
                    continue
                seen_pairs.add(pair)
                if estimate_jaccard(signatures[pair[0]], signatures[pair[1]]) >= threshold:
                    union(pair[0], pair[1])

    clusters: Dict[str, Set[str]] = {}
    for doc in signatures:
        clusters.setdefault(find(doc), set()).add(doc)
    logger.info("Clustered %d docs into %d group(s), %d candidate pair(s)",
                len(signatures), len(clusters), len(seen_pairs))
    return list(clusters.values())

Observability & Compliance Metrics

Three KPIs keep near-duplicate detection legible. Candidate-pair ratio (LSH candidate pairs ÷ all possible pairs) shows how effectively banding pruned the comparison space — a healthy value is a tiny fraction, confirming the quadratic blowup was avoided. Cluster reduction (documents ÷ clusters) measures how much review volume the near-duplicate grouping removed. Borderline rate (pairs near the threshold ÷ compared pairs) flags how much manual confirmation the current threshold demands and signals when it needs tuning. Because every clustering decision is logged with the threshold and banding parameters in force, these metrics are also the record that the culling was governed and reproducible.

python

from prometheus_client import Gauge, Counter

ND_CANDIDATE_RATIO = Gauge("neardup_candidate_ratio", "Candidate pairs over all pairs")
ND_CLUSTERS = Counter("neardup_clusters_total", "Near-duplicate clusters formed")
ND_BORDERLINE = Counter("neardup_borderline_total", "Pairs within the manual-review band")


def record_clustering(n_docs: int, n_candidates: int, n_clusters: int, borderline: int) -> None:
    all_pairs = max(1, n_docs * (n_docs - 1) // 2)
    ND_CANDIDATE_RATIO.set(n_candidates / all_pairs)
    ND_CLUSTERS.inc(n_clusters)
    ND_BORDERLINE.inc(borderline)

Conclusion

Near-duplicate detection is what turns a pile of revisions, format-conversions, and quoted replies into reviewable clusters, and it is only tractable at ESI scale because MinHash and LSH replace exact, quadratic comparison with bounded-memory signatures and sub-quadratic candidate generation. Shingle normalized text, sign it with a fixed-length MinHash, tune the LSH banding so the S-curve’s midpoint sits at your similarity threshold, and cluster the candidate survivors with tiered gates that never cull on a probabilistic score alone. Version-control the threshold and banding, log every decision, and the near-duplicate layer delivers both the review-cost reduction and the reproducibility a defensible culling process requires.

Frequently Asked Questions

What is the difference between exact deduplication and near-duplicate detection?

Exact deduplication uses a cryptographic hash to collapse byte-identical files — a single changed byte makes two files different. Near-duplicate detection measures textual similarity, so it groups documents that are almost the same but not identical: drafts, format conversions, or emails quoted in later replies. Exact dedup is cheap and certain; near-dup is probabilistic and threshold-governed, which is why it feeds tiered review gates rather than silent suppression.

Why use MinHash and LSH instead of just comparing documents directly?

Because direct comparison is quadratic and impossible at scale — a million documents is on the order of 500 billion pairs. MinHash reduces each document to a fixed-length signature that estimates Jaccard similarity, bounding memory, and LSH buckets those signatures so only plausibly-similar documents are ever compared, avoiding the all-pairs blowup. Together they make similarity detection near-linear instead of quadratic, at the cost of a small, controllable amount of estimation error.

How do you keep near-duplicate culling defensible?

By never excluding a document from review on a probabilistic score alone and by making the process reproducible. Documents comfortably above the threshold cluster automatically, borderline pairs go to manual confirmation, and low-similarity items get independent review. The similarity threshold and LSH banding parameters are version-controlled, and every clustering decision is logged with the parameters in force, so any cluster can be explained and the same collection re-run yields the same result.

How many hash functions does a MinHash signature need?

Enough to estimate Jaccard to the precision your threshold requires. The estimation error shrinks as roughly one over the square root of the number of hashes, so 128 permutations give an error around ±0.09, and 256 tighten it further at double the storage and compute. The right count balances that precision against signature size; 128 is a common default that separates near-duplicates from unrelated documents reliably.

Tuning MinHash LSH Bands for Near-Duplicate Detection — placing the S-curve at your target threshold.
SimHash vs MinHash for Textual Near-Dupes — choosing the right similarity primitive.
Similarity Threshold Configuration — the governance layer for the threshold this subsystem applies.
Hash-Based Deduplication Strategies — the exact-match stage that runs before near-duplicate detection.
Cross-Matter Deduplication — extending similarity indexing across matters with case isolation.

Up one level: Deduplication & Family Grouping — the pipeline stage that reduces review volume defensibly.