k ache-hash: A dynamic, concurrent, and cache-efficient hash table for streaming k -mer operations

Area of Science:

• Computational genomics
• Data structures
• Bioinformatics

Background:

• Hash tables are crucial in computational genomics for processing k-mers, which have a streaming property.
• Existing dynamic hash tables neglect k-mer locality, while static structures lack dynamic update capabilities.

Purpose of the Study:

• Introduce k-ache-hash, the first dynamic, concurrent, and resizable hash table optimized for k-mer locality.
• Improve performance of genomic data processing by exploiting the streaming nature of k-mers.

Main Methods:

• Developed k-ache-hash using a multi-level design (Iceberg hashing) with minimizer-based hashing.
• Ensured consecutive k-mers map to the same buckets to maintain cache residency.

Main Results:

• k-ache-hash demonstrated 1.58-2.62x higher insertion throughput and up to 6.1x higher query throughput on the human genome compared to IcebergHT.
• Achieved 7.39x fewer cache misses and near-linear scaling to 16 threads.
• Theoretical analysis shows O(1/r) amortized cache misses for streaming k-mer operations.

Conclusions:

• k-ache-hash offers significant performance improvements for dynamic, concurrent, and local k-mer processing in genomics.
• The hash table supports dynamic resizing without compromising locality.
• The minimizer-based approach effectively exploits k-mer streaming properties for enhanced cache performance.