DataTerminology.comNEW
A sketching technique that estimates Jaccard similarity between sets by comparing hashed minimum values across permutations.
DESCRIPTION
MinHash approximates Jaccard similarity by hashing set elements and recording the minimum hash under multiple independent hash functions. The fraction of matching minima between two sets approximates their Jaccard index. It enables scalable near-duplicate detection, clustering, and similarity joins over large collections. When combined with locality-sensitive hashing, MinHash supports sublinear-time retrieval of similar items. Accuracy improves with more hash permutations at increased memory cost.
ALTERNATIVE DEFINITIONS
Wikipedia
MinHash is a technique for quickly estimating how similar two sets are, the similarity being the Jaccard coefficient of the sets.
Directly links MinHash to Jaccard similarity estimation.
Mining of Massive Datasets (MMDS)
The MinHash of a set is defined by applying a random permutation to the universe and taking the minimum permuted value in the set; the probability of equality equals the Jaccard similarity.
Formal definition with probability property central to MinHash.
RELATED TERMS
Jaccard Index Locality-Sensitive Hashing Shingling Near-Duplicate Detection Sketching Similarity Join
COMPETING TERMS
SimHash Exact Jaccard Similarity
KNOWLEDGE AREAS
Data Science AI Mathematics Data Engineering
TARGET AUDIENCE
Data Scientist AI Engineer MLOps Engineer Data Engineer
EXTERNAL SOURCES
- Wikipedia - MinHash
- MMDS - Canonical textbook chapter on MinHash.
- Apache DataSketches - Theta sketches as MinHash-like set sketches.
- Apache Spark - MinHash feature transformer in MLlib.
TOP QUESTIONS
What does MinHash estimate?
It estimates Jaccard similarity between sets by comparing signatures of minimum hash values across multiple independent permutations.
Category: Definition
How many hash permutations do I need for MinHash?
More permutations reduce variance; hundreds are common. The choice balances accuracy against memory and computation.
Category: Requirements
How does MinHash relate to Locality-Sensitive Hashing?
MinHash signatures can be banded into LSH to retrieve near-duplicates efficiently with sublinear search time.
Category: Implementation
What are common mistakes using MinHash?
Using non-independent or low-quality hashes increases bias, and small signature sizes yield high variance.
Category: Mistakes
When should I use MinHash versus SimHash?
Use MinHash for set/Jaccard similarity; use SimHash for vector/cosine similarity. They target different similarity measures.
Category: Alternatives
What is a hot topic around MinHash?
Compressed or weighted MinHash variants support importance-weighted sets and memory-efficient large-scale deployments.
Category: Topic
How do I generate shingles for MinHash?
Break documents into k-grams (e.g., character or word n-grams) to form sets, then compute MinHash signatures.
Category: Implementation
Is MinHash suitable for exact duplicate detection?
It detects near-duplicates efficiently but is probabilistic. For exact equality, use hashing like SHA-256 on canonicalized content.
Category: Risk
Where is MinHash used in practice?
Search engines, deduplication of web pages, recommendation systems, and clustering of large document collections.
Category: Example