MinHash
MinHash summarizes sets using minimum hash values to estimate their Jaccard similarity.
In the classic independent-coordinate construction, each coordinate keeps the minimum under one shared random permutation. For nonempty sets, the probability of equal minima is their intersection size divided by their union size; the fraction of matching coordinates estimates this ratio. Ordinary pairwise independence alone does not establish this collision identity. [1]
Union takes coordinatewise minima of compatible signatures. Preserve the item representation, hash function and width, permutation family, seed and coordinate order; equal lengths alone do not establish compatibility. Practical hash families need their own error analysis. [2]
Repeated occurrences of an unchanged identity do not change the signature. A signature match is not proof that the input byte streams are equal. In a constructed chunk example, set similarity stays 1/3 while the share of incoming bytes already present changes from 1/2 to 9/10 as chunk sizes change. [3]
This coordinate-matching construction differs from retaining several low-ranked hashes under one ordering. Theta sketches instead retain distinct hashes below a threshold and support set expressions. [4]
Relations
- related
- Jaccard similarity, Theta sketch, Data deduplication, Cryptographic hash function, Content-defined chunking
Citations
- Broder, Charikar, Frieze and Mitzenmacher. Min-Wise Independent Permutations. JCSS 60(3), 2000, pp. 632-633.
- datasketch MinHash implementation: signature comparison, union and permutation-scheme assumptions.
- Hesela. MinHash and deduplication denominators: exact finite-set illustration and tests.
- Apache DataSketches. Theta Sketch Framework: thresholded state and set operations.
Sources & caveats
- The worked examples enumerate ideal finite permutations and exact chunk identities, not a deployed MinHash library or storage workload. [3]