k-hash:一个动态的,并发的,缓存效率高的哈希表,用于流动 k-mer 操作.
bioRxiv : the preprint server for biology
|February 27, 2026
概括
我们开发了k-ache-hash,这是一个用于计算基因组学的新哈希表,它利用k-mer本地化来实现更快的数据流操作. 与现有方法相比,这种新结构显著改善了插入和查询吞吐量,同时减少了缓存错误.
科学领域:
- 计算基因组学是一种计算基因组学.
- 数据结构数据结构.
- 生物信息学是一种生物信息学.
背景情况:
- 哈希表在计算基因组学中对于处理k-mers至关重要,k-mers具有流媒体属性.
- 现有的动态哈希表忽略了k-mer局域,而静态结构缺乏动态更新功能.
研究的目的:
- 介绍了k-ache-hash,这是首个动态,并发和可调整大小的哈希表,针对k-mer地区进行了优化.
- 通过利用k-mers.的流媒体性质来提高基因组数据处理的性能.
主要方法:
- 使用多级设计 (冰山哈希) 开发了k-ache-hash,使用基于最小化器的哈希.
- 确保连续的 k-mers 映射到相同的桶中,以保持缓存的存在.
主要成果:
- 与IcebergHT.HT相比,k-ache-hash在人类基因组上的插入吞吐量是1.58-2.62倍,查询吞吐量高达6.1倍.
- 实现了7.39x更少的缓存错误和近线性扩展到16个线程.
- 理论分析显示,对于流式k-mer操作,O(1/r) 的摊销缓存缺失.
结论:
- 在基因组学中,k-ache-hash为动态,并发和本地k-mer处理提供了显著的性能改进.
- 哈希表支持动态调整大小,而不会影响局部性.
- 以最小化器为基础的方法有效地利用k-mer流媒体属性来提高缓存性能.
相关概念视频
Maximum Size of Aggregate
601
The maximum size of aggregate is defined as the aperture of the sieve retaining 15 percent or more of the particles present in the aggregate sample. The aggregate's maximum size impacts the concrete's water requirement, workability, and strength. Larger aggregates reduce the surface area needing cement paste coverage, which can lower water needs, thereby allowing a decrease in the water-to-cement ratio when the desired workability and richness of the mix are to be maintained, which can...
601
Parallel Processing
819
The brain processes sensory information rapidly due to parallel processing, which involves sending data across multiple neural pathways at the same time. This method allows the brain to manage various sensory qualities, such as shapes, colors, movements, and locations, all concurrently. For instance, when observing a forest landscape, the brain simultaneously processes the movement of leaves, the shapes of trees, the depth between them, and the various shades of green. This enables a quick and...
819
Stream Function
2.2K
In two-dimensional incompressible fluid flow, the continuity equation is essential for ensuring mass conservation, meaning that any change in fluid entering or exiting a region is balanced by a corresponding change elsewhere. For incompressible flow, where density remains constant, this requirement simplifies to the condition that the divergence of the velocity field must be zero. Mathematically, this is expressed as,
2.2K
Extraction: Partition and Distribution Coefficients
5.2K
The distribution law or Nernst's distribution law is the law that governs the distribution of a solute between two immiscible solvents. This law, also known as the partition law, states that if a solute is added to the mixture of two immiscible solvents at a constant temperature, the solute is distributed between the two solvents in such a way that the ratio of solute concentrations in the solvents remains constant at equilibrium.
For extracting a solute from an aqueous phase into an...
For extracting a solute from an aqueous phase into an...
5.2K
Multi-species Conserved Sequences
4.9K
Next-generation sequencing technologies have created large genomic databases of a variety of animals and plants. Ever since the human genome project was completed, scientists studied the genome of primates, mammals, and other phylogenetically distant living beings. Such large-scale studies have provided new insights into the evolutionary relationship between organisms.
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
4.9K
Rapidly Varying Flow
561
Rapidly varying flow (RVF) in open channels is characterized by abrupt changes in flow depth over a short distance, with the rate of depth change relative to distance often approaching unity. These flows are inherently complex due to their transient and multi-dimensional nature, making exact analysis difficult. However, approximate solutions using simplified models provide valuable insights into their behavior.Key Features of Rapidly Varying FlowRVF is commonly observed in scenarios involving...
561
