Cosine Similarity Estimation Using FracMinHash: Theoretical Analysis, Safety Conditions, and Implementation

Mahmudur Rahman Hera, David Koslicki

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Motivation. The increasing number and volume of genomic and metagenomic data necessitates scalable and robust computational models for precise analysis. Sketching techniques utilizing kmers from a biological sample have proven to be useful for large-scale analyses. In recent years, FracMinHash has emerged as a popular sketching technique and has been used in several useful applications. Recent studies on FracMinHash proved unbiased estimators for the containment and Jaccard indices. However, theoretical investigations for other metrics, such as the cosine similarity, are still lacking. Theoretical contributions. In this paper, we present a theoretical framework for estimating cosine similarity from FracMinHash sketches. We establish conditions under which this estimation is sound, and recommend a minimum scale factor s for accurate results. Experimental evidence supports our theoretical findings. Practical contributions. We also present frac-kmc, a fast and efficient FracMinHash sketch generator program. frac-kmc is the fastest known FracMinHash sketch generator, delivering accurate and precise results for cosine similarity estimation on real data. We show that by computing FracMinHash sketches using frac-kmc, we can estimate pairwise cosine similarity speedily and accurately on real data. frac-kmc is freely available here: https://github.com/KoslickiLab/frac-kmc/.

Original languageEnglish (US)
Title of host publication24th International Workshop on Algorithms in Bioinformatics, WABI 2024
EditorsSolon P. Pissis, Wing-Kin Sung
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959773409
DOIs
StatePublished - Aug 2024
Event24th International Workshop on Algorithms in Bioinformatics, WABI 2024 - London, United Kingdom
Duration: Sep 2 2024Sep 4 2024

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume312
ISSN (Print)1868-8969

Conference

Conference24th International Workshop on Algorithms in Bioinformatics, WABI 2024
Country/TerritoryUnited Kingdom
CityLondon
Period9/2/249/4/24

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Cosine Similarity Estimation Using FracMinHash: Theoretical Analysis, Safety Conditions, and Implementation'. Together they form a unique fingerprint.

Cite this