2026-07-24T12:23:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17974 2024-03-06T11:00:46Z ddc:004 open_access

Improving the Sensitivity of MinHash Through Hash-Value Analysis Kucherov, Gregory Skiena, Steven MinHash sketching sequence similarity hashing MinHash sketching is an important algorithm for efficient document retrieval and bioinformatics. We show that the value of the matching MinHash codes convey additional information about the Jaccard similarity of S and T over and above the fact that the MinHash codes agree. This observation holds the potential to increase the sensitivity of minhash-based retrieval systems. We analyze the expected Jaccard similarity of two sets as a function of observing a matching MinHash value a under a reasonable prior distribution on intersection set sizes, and present a practical approach to using MinHash values to improve the sensitivity of traditional Jaccard similarity estimation, based on the Kolmogorov-Smirnov statistical test for sample distributions. Experiments over a wide range of hash function counts and set similarities show a small but consistent improvement over chance at predicting over/under-estimation, yielding an average accuracy of 61% over the range of experiments. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gregory Kucherov and Steven Skiena 2023 Is Part Of LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2023.20 urn:nbn:de:0030-drops-179740 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.20 eng https://creativecommons.org/licenses/by/4.0/legalcode