You’ve probably been there: staring at a massive dataset of millions of documents, images, or user profiles, desperately trying to deduplicate them before your pipeline collapses under its own weight. You search for a lifeline and discover MinHash. It promises to approximate Jaccard similarity at scale, trading a tiny bit of exactness for massive speed. It sounds like a miracle.
Most people implement MinHash wrong because they trust the wrong tutorials, and they end up killing the very algorithm they’re trying to use.
The core idea of MinHash is brilliant: by using random hash functions, you can estimate the similarity between two sets without comparing every single element. It bypasses the nightmare of pairwise comparisons. But there is a massive, glaring trap hidden in many explanations that will silently corrupt your results.
The trap is this: tutorials repeatedly claim that the hash functions you apply to each element should be “locality-preserving.” The logic seems sound on the surface. If you want to find similar items, shouldn’t similar inputs produce similar hashes? It feels intuitive. It feels safe.
If your hash function is locality-preserving, your MinHash implementation is fundamentally broken.
Here is the twist: MinHash does not want your hashes to be smart. It doesn’t want them to understand the “neighborhood” of your data. The entire probabilistic guarantee of MinHash—that the minimum hash of a set equals the minimum hash of a union—relies on one strict condition. The hash functions must be completely, utterly, and chaotically random.
When you use a locality-preserving hash, you introduce bias. You cluster similar items together in the hash space, which destroys the uniform probability distribution that MinHash mathematically requires. You are trying to help the algorithm, but you are actually stripping away its mathematical armor.
You can’t cheat randomness. The moment you try to make hashes ‘smart,’ you break the foundation of the approximation.
If you are working with large-scale text, image, or graph data, you need to audit your MinHash implementation today. If your hash functions are preserving locality, rip them out. Replace them with standard, well-vetted random hash functions like MurmurHash or xxHash. The goal isn’t to group similar things; it’s to scatter everything uniformly so that probability can do the heavy lifting.
Stop reinventing the wheel and stop copying bad code. Scale doesn’t forgive bad math—it amplifies it. Respect the randomness, and let MinHash do what it was designed to do.
FAQ
Q: Why does it matter if the hashes are locality-preserving? It seems more efficient.
A: It's not about efficiency; it's about mathematical correctness. Locality-preserving hashes introduce bias that destroys the uniform probability distribution MinHash relies on to approximate Jaccard similarity.
Q: What kind of hash functions should I actually use?
A: Use standard, well-vetted random hash functions like MurmurHash or xxHash. The key is uniform distribution across the hash space, not similarity preservation.
Q: Is MinHash even worth the complexity when we have vector embeddings now?
A: For massive-scale near-duplicate detection, absolutely. Embeddings are great for semantic search, but they are overkill and too slow for exact or near-exact deduplication where MinHash shines.