MinHash

MinHash provides an unbiased estimator of the Jaccard index between two sets. The probability that the minimum hash value of set A equals the minimum hash value of set B is exactly equal to their Jaccard similarity. By using k independent hash functions, the fraction of matching minimum values converges to the true Jaccard coefficient, with the estimation error decreasing proportionally to 1/√k.

A compact signature matrix is constructed by applying multiple hash functions to each element of a set and recording only the minimum hash value per function. Key properties:

• Dimensionality reduction: A set of arbitrary size is compressed into a fixed-length vector of k integers
• Linearity: The signature size is independent of the original set cardinality
• Streaming compatibility: Signatures can be updated incrementally as new elements arrive

To efficiently find similar pairs without comparing all signatures, the signature vector is partitioned into b bands of r rows each. Two sets become a candidate pair if they share identical values in at least one band. This creates a tunable trade-off:

• Larger b (more bands): Increases recall, finds more candidate pairs
• Larger r (more rows per band): Increases precision, reduces false positives
• The probability of becoming a candidate pair follows an S-curve that steepens with more bands

The classic MinHash algorithm uses random permutations of the element universe. For each permutation, the element with the smallest permuted index becomes the signature value. In practice, universal hash functions of the form h(x) = (ax + b) mod p approximate random permutations efficiently without materializing the full permutation array, enabling processing of massive datasets with minimal memory overhead.

MinHash is the foundational algorithm behind large-scale document deduplication and plagiarism detection systems. By representing documents as sets of n-grams or shingles, MinHash signatures enable:

• Web crawl deduplication: Removing identical pages from search indexes
• Code clone detection: Identifying similar source code fragments
• Content moderation: Finding near-duplicate user-generated content across platforms

While both are LSH techniques for similarity detection, they serve different distance metrics:

• MinHash: Estimates Jaccard similarity (set overlap), ideal for document shingle comparison
• SimHash: Produces a fixed-width binary fingerprint where Hamming distance correlates with cosine similarity, better for near-duplicate detection with bitwise operations
• MinHash signatures are typically larger but provide a direct probabilistic guarantee on Jaccard estimation

The foundational set similarity metric that MinHash estimates. It measures the size of the intersection divided by the size of the union of two sets.

• Formula: J(A,B) = |A ∩ B| / |A ∪ B|
• Range: 0 (completely disjoint) to 1 (identical)
• MinHash Connection: The probability that two sets have the same minimum hash value equals their Jaccard similarity
• Use Case: Document near-duplicate detection, where each document is represented as a set of shingles (n-grams)

An algorithmic framework that hashes similar items into the same buckets with high probability. MinHash is a specific LSH family for Jaccard similarity.

• Core Principle: Hash collisions are maximized for similar inputs and minimized for dissimilar ones
• Band Partitioning: MinHash signatures are divided into bands; if any band matches exactly between two documents, they become a candidate pair
• Amplification: Using multiple bands and rows per band allows precise tuning of the similarity threshold
• Efficiency: Reduces pairwise comparisons from O(n²) to sub-linear time

The preprocessing step that converts a document into a set of contiguous subsequences (shingles) before MinHash is applied.

• k-Shingles: Typically k=5 to 9 for text documents, representing word or character n-grams
• Tokenization: Documents are normalized (lowercased, punctuation stripped) before shingle extraction
• Set Representation: Each unique shingle becomes an element in the set; ordering is discarded
• Example: The phrase "the cat sat" yields 3-shingles: {"the cat sat", "cat sat on", "sat on the", "on the mat"}

A compact, fixed-length vector of minimum hash values that serves as a dimensionality-reduced proxy for the original set.

• Construction: Apply N independent hash functions to each element; keep only the minimum hash value per function
• Length: Typically 100-500 hash functions, balancing accuracy against storage
• Estimation: The fraction of matching positions between two signatures approximates Jaccard similarity
• Storage Efficiency: A 128-signature MinHash using 32-bit integers requires only 512 bytes per document, regardless of original set size

A related but distinct dimensionality reduction technique that produces a compact fingerprint where similar documents have a small Hamming distance.

• Mechanism: Uses a single hash function per feature, weighted by term frequency, and aggregates sign bits
• Key Difference: SimHash produces a single fixed-width fingerprint; MinHash produces a vector of minimum values
• Similarity Metric: Hamming distance (bit differences) vs. Jaccard similarity
• Best For: Near-duplicate detection where bitwise XOR comparison speed is critical, such as web crawling at Google's scale

A space-efficient probabilistic data structure often used alongside MinHash for rapid set membership testing with controllable false positive rates.

• Guarantee: No false negatives; if the filter says an element is absent, it definitely is
• Integration: Can pre-filter candidate pairs before expensive MinHash signature comparisons
• Trade-off: Memory usage vs. false positive probability, configured via bit array size and number of hash functions
• Example: A Bloom filter with 1% false positive rate requires ~9.6 bits per element