Overview
MinHash stores the minimum hash value under several hash functions, making Jaccard similarity estimable without comparing full sets.
CoreSource checked
MinHash
Estimates set similarity by comparing compact hash signatures.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Intermediate
- Family
- Similarity Hashing
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
jaccard similarityhash signatureminimum hashset sketch
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(k n)
Average
O(k n)
Worst
O(k n)
Space
O(k)
When to Use
- Use when text search needs jaccard similarity.
- Use when the input matches the assumptions behind similarity Hashing.
When Not to Use
- Avoid when a simpler exact search is enough and approximate scoring is unnecessary.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Estimates set similarity by comparing compact hash signatures
- Uses jaccard similarity and hash signature to guide the work.
- Produces matches.
Use Cases
- Text search
- Sequence comparison
- Similarity detection
Inputs
- Pattern or query sequence
- Text or target sequence
Outputs
- Matches
- Score
- Alignment or index
Key Formulas (1)
MinHash estimate
similarity ≈ matchingsignatures / signaturecount
similarity ~= matching_signatures / signature_countEstimates Jaccard similarity from equal signature components.
Pseudocode
- 1.Prepare the inputs and state needed for MinHash.
- 2.Apply the jaccard similarity step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return matches.
Canonical Example
- Input
- MinHash with a minimal inspectable input
- Output
- Matches
- Explanation
- MinHash applies jaccard similarity to produce matches.
Implementation Notes
- Normalize input consistently before building indexes or comparing sequences.
- Keep the jaccard similarity step separate enough to test independently.
Common Pitfalls
- Changing tokenization or distance definitions changes the match result.
- Forgetting to check edge cases can make MinHash look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow matched positions, dynamic-programming cells, or candidate buckets.
Input:ABABABCABAB
Window:ABAB
Step 1 of 4: Prepare the inputs and state needed for MinHash.
pattern-matching-mechanismNotes
MinHash should be used with the assumptions and tradeoffs of similarity Hashing in mind.
Sources (2)
What each reference supports for this entry.
Broder MinHash
PaperReference for MinHash sketches and resemblance estimation using minimum hash values.
Open sourceMining of Massive Datasets
BookLarge-scale data-mining reference covering MinHash similarity estimation, sketching, or vector comparison use case.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used byLocality-Sensitive Hashing
Pattern Matching · Core
MinHash signatures are often indexed with LSH for approximate similarity search.
Compare with thisRelationships
View full relationship pageApproximatesJaro-Winkler Distance
MinHash approximates set similarity rather than character-level string similarity.
Used byLocality-Sensitive Hashing
MinHash signatures are often indexed with LSH for approximate similarity search.
Related Algorithms
Tags
Pattern MatchingHashingSimilarityProbabilistic Data Structure