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

Abstract

Many computational genomic analyses spend much of their time inserting and looking up k-mers in large hash tables. These operations stream through sequences, and consecutive k-mers share k - 1 characters. General hash tables ignore this locality. Each k-mer costs them a memory access, and in concurrent builds, a synchronization. We present kache-hash, an exact, dynamic, concurrent, and resizable hash table that places k-mers by their minimizers. A run of consecutive k-mers with the same minimizer then shares its buckets, which it fetches and locks only once. Building on Iceberg hashing, kache-hash handles skewed minimizers with secondary buckets. A compact spill filter lets lookups stop early, yet stay exact. The table stores sets or maps, and doubles in place in parallel. Under a cache-residency assumption, we show that a run that stays in its primary bucket brings in at most that bucket's cache lines, however long the run is. We compare kache-hash with six general-purpose and k-mer-specific tables on five genomic datasets. At 56 threads, it builds k-mer sets 3.5--7.0x faster than the fastest baseline, and answers queries 1.5--5.4x faster. On the human genome, its positive and mixed queries fetch 3.1--3.2x fewer cache lines per k-mer than those of the fastest baseline. In PanGenie, kache-hash speeds up end-to-end genotyping 1.96x with identical outputs. In K2Rmini, it speeds up read filtering 10.7--19.4x over a fixed control version of the release, also making the filter exact. kache-hash is implemented in C++20 and is available at https://github.com/jamshed/kache-hash.