Dataset Information

HyperMinHash: MinHash in LogLog space.

ABSTRACT: In this extended abstract, we describe and analyze a lossy compression of MinHash from buckets of size O(logn) to buckets of size O(loglogn) 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 an additive approximation error ϵ on a Jaccard index t, given a random oracle, HyperMinHash needs O(ϵ-2(loglogn+log1ϵ)) space. HyperMinHash allows estimating Jaccard indices of 0.01 for set cardinalities on the order of 1019 with relative error of around 10% using 2MiB of memory; MinHash can only estimate Jaccard indices for cardinalities of 1010 with the same memory consumption.

SUBMITTER: Yu YW

PROVIDER: S-EPMC10824537 | biostudies-literature | 2022 Jan

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

HyperMinHash: MinHash in LogLog space.

Yu Yun William YW Weber Griffin M GM

IEEE transactions on knowledge and data engineering 20200317 1

In this extended abstract, we describe and analyze a lossy compression of MinHash from buckets of size O(logn) to buckets of size O(loglogn) 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, u ...[more]

PMID: 38288326

Similar Datasets

Project description:Space travel has advanced significantly over the last six decades with astronauts spending up to 6 months at the International Space Station. Nonetheless, the living environment while in outer space is extremely challenging to astronauts. In particular, exposure to space radiation represents a serious potential long-term threat to the health of astronauts because the amount of radiation exposure accumulates during their time in space. Therefore, health risks associated with exposure to space radiation are an important topic in space travel, and characterizing space radiation in detail is essential for improving the safety of space missions. In the first part of this review, we provide an overview of the space radiation environment and briefly present current and future endeavors that monitor different space radiation environments. We then present research evaluating adverse biological effects caused by exposure to various space radiation environments and how these can be reduced. We especially consider the deleterious effects on cellular DNA and how cells activate DNA repair mechanisms. The latest technologies being developed, e.g., a fluorescent ubiquitination-based cell cycle indicator, to measure real-time cell cycle progression and DNA damage caused by exposure to ultraviolet radiation are presented. Progress in examining the combined effects of microgravity and radiation to animals and plants are summarized, and our current understanding of the relationship between psychological stress and radiation is presented. Finally, we provide details about protective agents and the study of organisms that are highly resistant to radiation and how their biological mechanisms may aid developing novel technologies that alleviate biological damage caused by radiation. Future research that furthers our understanding of the effects of space radiation on human health will facilitate risk-mitigating strategies to enable long-term space and planetary exploration.

Dataset Information

HyperMinHash: MinHash in LogLog space.

Publications

HyperMinHash: MinHash in LogLog space.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets