MODULE 7/LESSON 1

🧹 AI Data Engineering & Deduplication

MinHash & Locality-Sensitive Hashing (LSH)

Deduplicate millions of documents in O(N) using MinHash signature vectors & Locality-Sensitive Hashing

⏱ 16 min⚡ Interactive Tool📊 Diagram

Deduplicating training data for LLMs (or cleaning vector database ingestion) is mandatory to prevent memorization and hallucination. However, exact pairwise Jaccard similarity calculation takes O(N²) time — requiring 50 trillion comparisons for just 10 million documents. MinHash LSH (Locality-Sensitive Hashing) reduces this to near-O(N) by generating fixed-size 'signatures' and hashing similar signatures into identical collision buckets.

Key Concepts

Shingling (n-grams)

First, documents are converted into overlapping word sets (shingles). For example, 3-grams: {'the quick brown', 'quick brown fox'}. This captures structure, unlike single words.

MinHash Signatures

Instead of comparing massive sets, MinHash runs k hash functions over the shingles and keeps only the minimum hash value for each. The probability that two documents share a min-hash equals their exact Jaccard Similarity.

LSH Banding (b x r)

Comparing k-length signatures is still O(N²). LSH splits the signature into b bands of r rows. If any band matches perfectly between two documents, they are hashed to the same bucket and flagged as candidates.

The S-Curve Math

Probability of collision follows the S-curve: P = 1 - (1 - s^r)^b. This creates a sharp threshold. Below the similarity threshold (s), probability is 0%. Above it, probability jumps to 100%.

⚡ Interactive Architecture Simulator

MinHash LSH & Banding Simulator

Hash Functions (k): 100

Bands (b): 20

Jaccard Similarity (s): 75%

5Rows / Band (r)r = k ÷ b

23.73%Band Match (s^r)per-band prob.

99.6%LSH Candidate P1-(1-s^r)^b

Duplicate ✓Dedup StatusLSH Bucket

LSH Banding Matrix — 12 of 20 bands

100 MinHash values ÷ 20 bands = 5 rows each. At 75% similarity → 99.6% bucket collision chance.

Band #1

5× hash sig

✗ No match

Band #2

5× hash sig

✗ No match

Band #3

5× hash sig

✗ No match

Band #4

5× hash sig

✗ No match

Band #5

5× hash sig

✗ No match

Band #6

5× hash sig

✗ No match

Band #7

5× hash sig

✗ No match

Band #8

5× hash sig

✗ No match

Band #9

5× hash sig

✗ No match

Band #10

5× hash sig

✗ No match

Band #11

5× hash sig

✗ No match

Band #12

5× hash sig

✗ No match

MinHash LSH Pipeline Architecture

Tuning the Math: Threshold Probability (k = 100 hashes)

Notice how the S-Curve mathematically separates duplicates from unique documents sharply around the target Jaccard similarity threshold.

Similarity (s)	P (b=20, r=5)	P (b=50, r=2)
10% similar	0.00% (No match)	40.10% (High false positives)
30% similar	0.04% (Ignored)	99.41% (Matches correctly)
70% similar	91.80% (Matches correctly)	100.00%
90% similar	100.00% (Perfect match)	100.00%

Production Code 1: Fast Python Deduplication (datasketch)

minhash_local_dedup.pypython
import re
from datasketch import MinHash, MinHashLSH

# ── 1. Text Preprocessing ────────────────────────────────────────────────
def tokenize_shingles(text: str, n: int = 3) -> set:
    """Extract character n-grams (shingles) from raw text."""
    text = re.sub(r'\s+', ' ', text.lower().strip())
    words = text.split(' ')
    return set(" ".join(words[i:i+n]) for i in range(max(1, len(words)-n+1)))

# ── 2. Create MinHash Signature ──────────────────────────────────────────
def create_minhash(text: str, num_perm: int = 128) -> MinHash:
    m = MinHash(num_perm=num_perm)
    for shingle in tokenize_shingles(text):
        m.update(shingle.encode('utf-8'))
    return m

# ── 3. Initialize LSH Index ──────────────────────────────────────────────
# Setting threshold=0.8 automatically computes optimal (b, r) for num_perm=128
# e.g., b=25, r=5
lsh = MinHashLSH(threshold=0.80, num_perm=128)

documents = {
    "doc_1": "NVIDIA Hopper architecture delivers massive performance gains for transformer models.",
    "doc_2": "The NVIDIA Hopper architecture provides massive performance improvements for transformer models.",
    "doc_3": "PostgreSQL indexing strategies using B-Trees and Hash indexes."
}

# ── 4. Indexing (O(N)) ───────────────────────────────────────────────────
for doc_id, content in documents.items():
    lsh.insert(doc_id, create_minhash(content))

# ── 5. Querying (O(1) lookup per query) ──────────────────────────────────
query_doc = "NVIDIA Hopper architecture yields massive performance gains on transformer models."
query_hash = create_minhash(query_doc)

candidates = lsh.query(query_hash)
print(f"Candidates for query: {candidates}")
# Output expected: ['doc_1', 'doc_2'] (doc_3 is completely ignored without being compared)

Production Code 2: PySpark Distributed LSH (10M+ Docs)

pyspark_lsh_pipeline.pypython
from pyspark.sql import SparkSession
from pyspark.ml.feature import Tokenizer, NGram, MinHashLSH

spark = SparkSession.builder.appName("LSH-Dedup").getOrCreate()

# Load massive dataset
df = spark.read.json("s3://llm-corpus/wikipedia_dump.jsonl")

# 1. Tokenize into words
tokenizer = Tokenizer(inputCol="text", outputCol="words")
wordsData = tokenizer.transform(df)

# 2. Generate 3-gram shingles
ngram = NGram(n=3, inputCol="words", outputCol="ngrams")
ngramData = ngram.transform(wordsData)

# 3. Create LSH Model with specific Bucket Length
# (In PySpark, bucketLength controls the collision probability, similar to threshold)
mh = MinHashLSH(inputCol="ngrams", outputCol="hashes", numHashTables=5, seed=42)
model = mh.fit(ngramData)

# 4. Find all duplicate pairs across the entire 10M document cluster!
# Computes near-O(N) distributed join based on LSH buckets
duplicate_pairs = model.approxSimilarityJoin(
    ngramData, 
    ngramData, 
    threshold=0.80, 
    distCol="JaccardDistance"
)

# Filter self-matches
duplicates = duplicate_pairs.filter("datasetA.id < datasetB.id")
duplicates.show(10)

💡

Senior Architect Insight: Do not blindly increase `num_perm` (e.g. k=512 or 1024) to get higher accuracy. More hashes exponentially increase RAM usage and slow down LSH insertion time. k=128 or k=256 is the industry sweet spot for deduplicating billions of tokens for LLM pre-training.

PreviousSocial Media Feed Architecture

Next LessonAdvanced Data Parsing & Semantic Chunking