# In Defense of MinHash Over SimHash

arXiv: https://arxiv.org/abs/1407.4416 · HTML: https://mlsanity.com/paper/1407.4416/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2014.

## Built on by (most cited first, 11 of 11)

- [Arena Learning: Build Data Flywheel for LLMs Post-training via Simulated Chatbot Arena](https://mlsanity.com/paper/2407.10627/) (2024)
- [pNLP-Mixer: an Efficient all-MLP Architecture for Language](https://mlsanity.com/paper/2202.04350/) (2022)
- [MRAMG-Bench: A Comprehensive Benchmark for Advancing Multimodal Retrieval-Augmented Multimodal Generation](https://mlsanity.com/paper/2502.04176/) (2025)
- [Differential Privacy with Random Projections and Sign Random Projections](https://mlsanity.com/paper/2306.01751/) (2023)
- [Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling](https://mlsanity.com/paper/2306.07674/) (2023)
- [C-MinHash: Rigorously Reducing K Permutations to Two](https://mlsanity.com/paper/2109.03337/) (2021)
- [Large-Scale Distributed Learning via Private On-Device Locality-Sensitive Hashing](https://mlsanity.com/paper/2306.02563/) (2023)
- [Unlock the Correlation between Supervised Fine-Tuning and Reinforcement Learning in Training Code Large Language Models](https://mlsanity.com/paper/2406.10305/) (2024)
- [Building Domain-Specific Small Language Models via Guided Data Generation](https://mlsanity.com/paper/2511.21748/) (2025)
- [Pb-Hash: Partitioned b-bit Hashing](https://mlsanity.com/paper/2306.15944/) (2023)
- [Improving LSH via Tensorized Random Projection](https://mlsanity.com/paper/2402.07189/) (2024)

## Abstract (arXiv)

MinHash and SimHash are the two widely adopted Locality Sensitive Hashing (LSH) algorithms for large-scale data processing applications. Deciding which LSH to use for a particular problem at hand is an important question, which has no clear answer in the existing literature. In this study, we provide a theoretical answer (validated by experiments) that MinHash virtually always outperforms SimHash when the data are binary, as common in practice such as search. The collision probability of MinHash is a function of resemblance similarity (R), while the collision probability of SimHash is a function of cosine similarity (S). To provide a common basis for comparison, we evaluate retrieval results in terms of S for both MinHash and SimHash. This evaluation is valid as we can prove that MinHash is a valid LSH with respect to S, by using a general inequality S2≤ R≤ fracS2-S. Our worst case analysis can show that MinHash significantly outperforms SimHash in high similarity region. Interestingly, our intensive experiments reveal that MinHash is also substantially better than SimHash even in datasets where most of the data points are not too similar to each other. This is partly because, in practical data, often R≥ fracSz-S holds where z is only slightly larger than 2 (e.g., z≤ 2.1). Our restricted worst case analysis by assuming fracSz-S≤ R≤ fracS2-S shows that MinHash indeed significantly outperforms SimHash even in low similarity region. We believe the results in this paper will provide valuable guidelines for search in practice, especially when the data are sparse.