In Defense of Minhash over Simhash
By Anshumali Shrivastava, Ping Li. 2014
119 citations recorded by the source corpus.
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 S 2
Subfields: Computer Vision and Pattern Recognition, Evaluation & Benchmarks
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Vision and Pattern Recognition
- Anshumali Shrivastava
- Ping Li
- Behnam Neyshabur
- Nati Srebro
- Sanjiv Kumar
- Yoshua Bengio
- Minjoon Seo
- Pascal Vincent
In Evaluation & Benchmarks
Citations in the corpus
- Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “Utilizing minwise hashing [2, 15], which is the LSH for resemblance and is known to outperform SRP in sparse data [23], we can construct an even better ALSH (i.”
- Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment (2015, methodology): “For sparse and high-dimensional binary dataset which are common over the web, it is known that minhash is typically the preferred choice of hashing over random projection based hash functions [39].”
- UNICORN: Runtime Provenance-Based Detector for Advanced Persistent Threats (2020, unknown): “Jaccard similarity [27] has been successfully applied in a variety of machine-learning-based real-world problems, such as document analysis [111] and malware classification [107] and detection [32].”
- Asymmetric Minwise Hashing (2014, background): “Interestingly, another recent work [38] has shown that for binary data (actually even sparse non-binary data), minhash can significantly outperform SRP for near neighbor search even as we evaluate both SRP and minhash in terms of the cosine similarity (although minhash is designed for resemblance).”