MinHash

MinHash provides an unbiased estimator of the Jaccard similarity coefficient between two sets. The probability that the minimum hash value of a random permutation is identical for two sets equals their Jaccard index.

• Jaccard Formula: J(A, B) = |A ∩ B| / |A ∪ B|
• MinHash Property: P[min(h(A)) = min(h(B))] = J(A, B)
• By comparing hundreds of independent minimum hashes, the exact Jaccard similarity is approximated with high accuracy.
• This transforms an O(n) set comparison into a fixed-size signature comparison.

A MinHash signature compresses a large set into a compact, fixed-length vector of integers. The signature length k determines the trade-off between accuracy and storage.

• Process: Apply k independent hash functions to each element of a set. For each hash function, keep only the minimum hash value observed.
• Result: A set of any size is reduced to a signature vector of length k.
• Example: A document shingled into 500 n-grams becomes a signature of just 100 integers.
• Storage Efficiency: Comparing two signatures of length k requires O(k) time instead of O(|A| + |B|) for exact Jaccard.

MinHash signatures are used directly within Locality-Sensitive Hashing (LSH) to perform private blocking. LSH bands the signature vector to ensure similar sets hash to the same bucket with high probability.

• Banding Technique: A signature of length k is divided into b bands of r rows each (where k = b * r).
• Collision Probability: The probability that two sets with Jaccard similarity s become a candidate pair is 1 - (1 - s^r)^b.
• Threshold Tuning: Adjusting b and r creates a sharp S-curve that approximates a similarity threshold, drastically reducing the number of pairwise comparisons.
• This is the core mechanism enabling private blocking in PPRL without revealing plaintext similarity.

MinHash relies on a family of independent, uniformly distributed hash functions. Cryptographic hash functions like SHA-256 are too slow for generating hundreds of permutations, so faster alternatives are used.

• Universal Hashing: Functions of the form h(x) = (ax + b) mod p where p is a large prime provide sufficient independence for MinHash.
• One-Permutation Hashing: A memory-efficient variant that uses a single permutation and partitions the hash space, reducing computational cost for large k.
• Densified One Permutation Hashing: Handles empty bins in one-permutation hashing by borrowing values from neighboring bins, maintaining unbiased estimation.
• These optimizations make MinHash practical for datasets with billions of elements.

In PPRL, MinHash is applied to encoded identifiers like Bloom filters or CLKs to enable private blocking. The technique reveals only the block assignment, not the raw similarity.

• Workflow: 1) Encode identifiers into a privacy-preserving representation (e.g., hardened Bloom filter). 2) Generate MinHash signatures from the encoded bit-vectors. 3) Apply LSH banding to assign records to blocks.
• Privacy Guarantee: The blocking process operates on already-encoded data, so even if an adversary observes the blocks, they learn only that certain encoded records are likely similar.
• Efficiency Gain: Reduces the quadratic comparison space of all-pairs linkage to linear or near-linear complexity by comparing only records within the same LSH bucket.
• This makes PPRL scalable to national-scale health data linkage projects.

Before MinHash can be applied to text, documents must be converted into sets of shingles (contiguous subsequences of tokens or characters).

• Word Shingling: A document becomes a set of overlapping word n-grams (e.g., 'the quick brown' for 3-word shingles).
• Character Shingling: More robust to spelling variations; uses character-level n-grams (e.g., 4-grams).
• Hashing Shingles: Large shingle sets are often compacted by hashing each shingle to a 32-bit or 64-bit integer to reduce memory.
• Example: The phrase 'privacy preserving record linkage' yields 3-word shingles: {'privacy preserving record', 'preserving record linkage'}.
• Shingling is the critical preprocessing step that bridges raw text and MinHash-based similarity estimation.