{"doi":"10.1109/tkde.2020.2981311","title":"HyperMinHash: MinHash in LogLog space","abstract":"In this extended abstract, we describe and analyze a lossy compression of MinHash from buckets of size <inline-formula><tex-math notation=\"LaTeX\">$O(\\log n)$</tex-math></inline-formula> to buckets of size <inline-formula><tex-math notation=\"LaTeX\">$O(\\log \\log n)$</tex-math></inline-formula> by encoding using floating-point notation. This new compressed sketch, which we call HyperMinHash, as we build off a HyperLogLog scaffold, can be used as a drop-in replacement of MinHash. Unlike comparable Jaccard index fingerprinting algorithms in sub-logarithmic space (such as b-bit MinHash), HyperMinHash retains MinHash's features of streaming updates, unions, and cardinality estimation. For a additive approximation error <inline-formula><tex-math notation=\"LaTeX\">$\\epsilon$</tex-math></inline-formula> on a Jaccard index <inline-formula><tex-math notation=\"LaTeX\">$ t$</tex-math></inline-formula> , given a random oracle, HyperMinHash needs <inline-formula><tex-math notation=\"LaTeX\">$O\\left(\\epsilon ^{-2} \\left(\\log \\log n + \\log \\frac{1}{ \\epsilon } \\right)\\right)$</tex-math></inline-formula> space. HyperMinHash allows estimating Jaccard indices of 0.01 for set cardinalities on the order of <inline-formula><tex-math notation=\"LaTeX\">$10^{19}$</tex-math></inline-formula> with relative error of around 10 percent using 2MiB of memory; MinHash can only estimate Jaccard indices for cardinalities of <inline-formula><tex-math notation=\"LaTeX\">$10^{10}$</tex-math></inline-formula> with the same memory consumption.","journal":"IEEE Transactions on Knowledge and Data Engineering","year":2020,"id":115472,"datarank":0.0,"base_score":0.0,"endowment":0.0,"self_citation_contribution":0.0,"citation_network_contribution":0.0,"self_endowment_contribution":0.0,"citer_contribution":0.0,"corpus_percentile":null,"corpus_rank":null,"citation_count":2,"citer_count":0,"citers_with_citation_signal":0,"citers_with_endowment":0,"datacite_reuse_total":0,"is_dataset":false,"is_dataset_confidence":0.9459,"is_data_producer":false,"deposit_databanks":null,"is_oa":true,"file_count":0,"downloads":0,"has_version_chain":false,"published_date":"2020-01-01","fair_score":null,"fair_percentile":null,"algorithm_id":"datarank_citation_only_1hop_v6","ranking_scope":"data_only","authors":[{"id":39725,"name":"Griffin M. Weber","orcid":"0000-0002-2597-881X","position":1,"is_corresponding":false},{"id":23992,"name":"Yun William Yu","orcid":"0000-0002-8275-9576","position":0,"is_corresponding":true}],"reference_count":28,"raw_metadata":null,"created_at":"2026-07-18T23:13:36.820928Z","pmid":"38288326","pmcid":null,"fwci":null,"citation_percentile":null,"influential_citations":0,"oa_status":null,"license":null,"views":0,"total_file_size_bytes":0,"version_count":0,"fair_f":null,"fair_a":null,"fair_i":null,"fair_r":null,"fair_zscore":null,"fair_rationale":null,"fair_model":null,"fair_agent_version":null,"fair_fulltext_source":null,"fair_has_llm":null,"fair_computed_at":null,"clinical_trials":[],"software_tools":[],"db_accessions":[],"linked_datasets":[],"topics":[]}