相关实验视频

Updated: Jul 4, 2025

Heuristic Mining of Hierarchical Genotypes and Accessory Genome Loci in Bacterial Populations

Heuristic Mining of Hierarchical Genotypes and Accessory Genome Loci in Bacterial Populations

Published on: December 7, 2021

超级MinHash: 在LogLog空间中的MinHash

Yun William Yu¹, Griffin M Weber²

¹Department of Mathematics, University of Toronto, Toronto, Ontario, Canada M5S 2E4.

IEEE transactions on knowledge and data engineering

|January 30, 2024

概括

我们介绍了HyperMinHash,这是一个压缩的MinHash草图,用于高效的Jaccard指数估计. 这种方法提供了在子对数空间中改进的枢密度估计,优于传统的MinHash.

科学领域:

计算机科学计算机科学
数据结构数据结构
算法算法是一种算法.

背景情况:

MinHash 是用于 Jaccard 指数估计的广泛使用的算法.
现有的压缩的MinHash变体通常会牺牲诸如流媒体更新或联盟等必不可少的功能.
亚对数空间算法在保持准确性和功能方面面临着挑战.

研究的目的:

为MinHash草图开发一种新的损耗压缩技术.
介绍HyperMinHash,一个与HyperLogLog兼容的压缩草图.
为了保留MinHash的核心功能,同时减少内存足迹.

主要方法:

使用浮点符号的MinHash的损耗压缩.
在HyperLogLog脚手架上构建HyperMinHash草图.
分析时空复杂性和准确性权衡.

主要成果:

HyperMinHash 在 Jaccard 索引上以空间实现了加法近似误差 .
用 2MiB 估计 0.01 的 Jaccard 索引,对 cardinalities 进行估计,使用 2MiB 的 ~10% 的相对误差.
在同样的内存约束下,在更大的枢纽数中估计Jaccard指数时优于MinHash.

结论:

HyperMinHash提供了一个空间高效的替代MinHash用于Jaccard指数估计.
它保留了诸如流媒体更新和联盟等必不可少的功能,这对于大数据应用至关重要.
允许对具有有限内存资源的大型数据集进行准确的 Jaccard 索引估计.

关键词:

压缩压缩的压缩方式超级日志 (hyperlog) 日志精细的哈希处理是明智的哈希.绘制草图,绘制草图.流动的流动流动的流动流动.

更多相关视频

Modeling the Size Spectrum for Macroinvertebrates and Fishes in Stream Ecosystems

Modeling the Size Spectrum for Macroinvertebrates and Fishes in Stream Ecosystems

Published on: July 30, 2019

In Vitro Reconstitution of Self-Organizing Protein Patterns on Supported Lipid Bilayers

In Vitro Reconstitution of Self-Organizing Protein Patterns on Supported Lipid Bilayers

Published on: July 28, 2018

相关概念视频

Modified Boxplots

Modified Boxplots

A standard box and whisker plot informs us about the spread of the data in a given sample. One can identify the minimum value, maximum value, first quartile value, second quartile or median value, and third quartile.
However, the box plot does not tell the reader about outliers - values that lie far from the center of the data. We can modify the standard box and whisker plot to identify the outliers and visualize the actual spread of the data in a sample.
Initially, we calculate the adjusted...

Hybridization of Atomic Orbitals I

Hybridization of Atomic Orbitals I

The mathematical expression known as the wave function, ψ, contains information about each orbital and the wavelike properties of electrons in an isolated atom. When atoms are bound together in a molecule, the wave functions combine to produce new mathematical descriptions that have different shapes. This process of combining the wave functions for atomic orbitals is called hybridization and is mathematically accomplished by the linear combination of atomic orbitals. The new orbitals that...

¹H NMR of Labile Protons: Temporal Resolution

¹H NMR of Labile Protons: Temporal Resolution

Protons bonded to heteroatoms such as nitrogen and oxygen exhibit a range of chemical shift values. This is due to the varying degree of hydrogen bonding between the proton and the heteroatom in other molecules. The extent of hydrogen bonding affects the electron density around the proton, thereby giving different chemical shift values for the protons in the proton NMR spectrum.
The –OH proton in alcohols typically appears in the range of δ 2 to 5 ppm but can vary depending on the specific...

¹H NMR: Complex Splitting

¹H NMR: Complex Splitting

A proton M that is coupled to a proton X results in doublet signals for M. However, NMR-active nuclei can be simultaneously coupled to more than one nonequivalent nucleus. When M is coupled to a second proton A, such as in styrene oxide, each peak in the doublet is split into another doublet.
Splitting diagrams or splitting tree diagrams are routinely used to depict such complex couplings. While drawing splitting diagrams, the splitting with the larger coupling constant is usually applied...

Sign Test for Matched Pairs

Sign Test for Matched Pairs

The sign test for matched pairs offers a robust method for comparing two paired samples, often for the effects of an intervention in one of them. This method is very useful in situations where the underlying distribution of the data is unknown. The test compares two related samples—often pre- and post-treatment measurements on the same subjects—to determine if there are significant differences in their median values.
To conduct the sign test, we first calculate the differences in...

Interpreting ¹H NMR Signal Splitting: The (n + 1) Rule

Interpreting ¹H NMR Signal Splitting: The (n + 1) Rule

In the AX proton spin system, proton A can sense the two spin states of a coupled proton X, resulting in a doublet NMR signal with two peaks of equal (1:1) intensity. When proton A is coupled to two equivalent protons (AX2 spin system), the spin states of each X can be aligned with or against the external field, creating three possible scenarios. This results in a 1:2:1 triplet signal, where the central peak corresponds to the chemical shift of A and is twice as large or intense as the...