Ragnar Groot Koerkamp

Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders et al.

A minimal perfect hash function (minimal PHF) is a data structure mapping a static set of $n$ keys to $n$ bins without collisions. Two natural generalizations are minimal $k$-PHFs where $n$ keys are mapped to $n/k$ bins of capacity $k$ each, and (non-minimal) PHFs with load factor $α < 1$ where the number of bins is increased by a factor of $1/α$, resulting in spare capacity. While there has been a recent surge of interest in perfect hashing generally, non-minimal $k$-PHFs have not been systematically studied despite a natural use case of speeding up static hash tables: The idea is that a small cache-resident $k$-PHF maps each key $x$ to a cache-line-sized bin of capacity $k$ where $x$ resides. Ideally, this yields a branchless lookup operation with a single cache miss working at high load factors for positive and negative queries alike. Our main theoretical contribution is to determine tight space lower bounds for $k$-PHFs for all pairs of $α \in (0,1]$ and $k \geq 1$. It turns out that combining $α < 1$ and $k \geq 2$ drastically reduces the space of $k$-PHFs, e.g. for $(k,α) = (16,0.8)$ the space lower bound is $0.027$ bits per key while for $(k,α) = (16,1.0)$ and $(k,α) = (1,0.8)$ the lower bounds are higher by factors of $\approx 8$ and $\approx 32$, respectively. On the practical side, we develop a $k$-PHF based on PtrHash and tune it for use in static hash tables. Empirically, our implementation produces $k$-PHFs of size roughly $50\%$ above the lower bound. A static hash set based on this $k$-PHF is consistently at least as fast as other hash sets for negative and mixed queries. On two of the three tested architectures it achieves up to $1.5\times$ speedup for large $n\geq 30M$ where a $1$-PHF does not fit in cache.

Nicola Rizzo, Ragnar Groot Koerkamp

Colinear chaining is a classical heuristic for sequence alignment: it enables scalable genome comparison and is a main component of many state-of-the-art read mappers based on seed-chain-extend. The earliest $O(n \log \log n)$ time algorithms by Eppstein et al. (J. ACM, 1992) chained $n$ fragments between two sequences $T$ and $Q$ while minimizing a gap cost based on the diagonal distance $Δ_{\text{diag}}$ between consecutive fragments. They also forbid fragment overlaps, which are essential in current chaining formulations: in long-read mapping, overlaps improve sensitivity and avoid restrictions on the fragment class considered. Jain, Gibney, and Thankachan (J. Comput. Biol. 2022) recently combined a $Δ_{\text{diag}} = |Δ_T -Δ_Q|$ overlap cost with the classic $L_\infty = \max(Δ_T , Δ_Q)$ gap cost that takes the maximum between the horizontal and vertical gap between the fragments and they proved that chaining under this cost model is equivalent to the anchored edit distance. We improve the existing $O(n \log^3 n)$-time algorithm for anchored edit distance to $O(n \log \log n)$ time in $O(n)$ space, by combining the gap-cost computation of Chao and Miller (Algorithmica, 1995) with the overlap-cost computation of Baker and Giancarlo (ESA, 1998). By developing llchain, a simpler $O(n \log n)$-time implementation of our method, we show how chaining algorithms that might have been recently overlooked by the bioinformatics community scale competitively to millions of fragments and large genomes. On average, llchain is $10\times$ faster than other methods on instances with $3\,000\,000$ anchors, and over $3\times$ faster on MEMs between HiFi reads and a reference human genome.