minhash · shipping · also min-wise hashing, minwise hashing

MinHash

MinHash summarizes sets using minimum hash values to estimate their Jaccard similarity.

Related Observatory article: Read on hesela.com

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

  1. Broder, Charikar, Frieze and Mitzenmacher. Min-Wise Independent Permutations. JCSS 60(3), 2000, pp. 632-633. (accessed 2026-11-20)
  2. datasketch MinHash implementation: signature comparison, union and permutation-scheme assumptions. (accessed 2026-11-20)
  3. Hesela. MinHash and deduplication denominators: exact finite-set illustration and tests. (accessed 2026-11-20)
  4. Apache DataSketches. Theta Sketch Framework: thresholded state and set operations. (accessed 2026-11-20)
Sources & caveats
  • The worked examples enumerate ideal finite permutations and exact chunk identities, not a deployed MinHash library or storage workload. [3]

JSON: /data/terms/minhash.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. MinHash. Hesela. 2026-11-20. https://hesela.dev/terms/minhash/