Search Results

Documents authored by Groot Koerkamp, Ragnar

Artifact
Software
DOI: 10.4230/artifacts.27683
nrizzo/llchain

Authors: Nicola Rizzo and Ragnar Groot Koerkamp

Abstract
Cite as

Nicola Rizzo, Ragnar Groot Koerkamp. nrizzo/llchain (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27683,
   title = {{nrizzo/llchain}}, 
   author = {Rizzo, Nicola and Groot Koerkamp, Ragnar},
   note = {Software, EU Horizon Europe 101060011, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:78de8057c7f61afc5518ef3b8a46a5ac91e21d52;origin=https://github.com/nrizzo/llchain;visit=swh:1:snp:0ea3e28442f7bc3c5f7db15d9b6314e87292c681;anchor=swh:1:rev:b0953ab025e078ab055a2ecf79221e119cad4922}{\texttt{swh:1:dir:78de8057c7f61afc5518ef3b8a46a5ac91e21d52}} (visited on 2026-08-27)},
   url = {https://github.com/nrizzo/llchain},
   doi = {10.4230/artifacts.27683},
}
Artifact
Software
DOI: 10.4230/artifacts.27679
RagnarGrootKoerkamp/minimizers

Authors: Ragnar Groot Koerkamp

Abstract
Cite as

Ragnar Groot Koerkamp. RagnarGrootKoerkamp/minimizers (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27679,
   title = {{RagnarGrootKoerkamp/minimizers}}, 
   author = {Groot Koerkamp, Ragnar},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:6b775d1315385c94ecbd6058cfbba2476fbeb0b4;origin=https://github.com/RagnarGrootKoerkamp/minimizers;visit=swh:1:snp:d0de14555d7455fd9cd1dc435feb0a29a559918c;anchor=swh:1:rev:61517a33b5f6b6eac7d7fd2d2ac39b1c27d28692}{\texttt{swh:1:dir:6b775d1315385c94ecbd6058cfbba2476fbeb0b4}} (visited on 2026-08-27)},
   url = {https://github.com/RagnarGrootKoerkamp/minimizers},
   doi = {10.4230/artifacts.27679},
}
Document
DOI: 10.4230/LIPIcs.WABI.2026.13
Revisiting O(n log log n) Chaining for Anchored Edit Distance

Authors: Nicola Rizzo and Ragnar Groot Koerkamp

Published in: LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026)

Abstract
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) and O(n 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 Δ_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 Δ_diag = |Δ_T-Δ_Q| overlap cost with the classic L_∞ = 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³ 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× faster than other methods on instances with 3 000 000 anchors, and over 2.3× faster on MEMs between HiFi reads and a reference human genome.
Cite as

Nicola Rizzo and Ragnar Groot Koerkamp. Revisiting O(n log log n) Chaining for Anchored Edit Distance. In 26th International Conference on Algorithms for Bioinformatics (WABI 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 390, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{rizzo_et_al:LIPIcs.WABI.2026.13,
  author =	{Rizzo, Nicola and Groot Koerkamp, Ragnar},
  title =	{{Revisiting O(n log log n) Chaining for Anchored Edit Distance}},
  booktitle =	{26th International Conference on Algorithms for Bioinformatics (WABI 2026)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-446-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{390},
  editor =	{El-Mabrouk, Nadia and Vandin, Fabio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.13},
  URN =		{urn:nbn:de:0030-drops-275177},
  doi =		{10.4230/LIPIcs.WABI.2026.13},
  annote =	{Keywords: Colinear chaining, Anchored edit distance, Sequence alignment, Predecessor structure}
}
Document
DOI: 10.4230/LIPIcs.WABI.2026.22
The Anti-Lexicographic SUS-Anchor: An Empirically Optimal Selection Scheme

Authors: Ragnar Groot Koerkamp

Published in: LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026)

Abstract
- Motivation. Selection schemes provide a way to select a subset of positions in a text in such a way that no two consecutive selected positions are more than w apart. These selected positions can be used as "anchor" points for text indices such that every sufficiently long pattern corresponds to at least one anchor [Ayad et al., 2025]. Closely related are sampling schemes, that sample a k-mer from each window of w consecutive k-mers in a text, and the more restricted minimizer schemes, that achieve this by taking the smallest k-mer according to some order. In recent years, there has been a renewed interest in the search for low density schemes that select/sample only a small fraction of positions/k-mers. The mod-minimizer [Groot Koerkamp and Pibiri, 2024] provides a near-optimal density of 1/w as k / w → ∞, while schemes such as the greedy minimizer work well for explicit small parameters roughly in the regime k ≤ 2w, for k and w up to 15 or so. When k < log_σ w is small, minimizer schemes cannot do well [Marçais et al., 2018]. As a first step towards low density sampling schemes in this regime, we fix k = 1 and search for a near-optimal selection scheme to improve the existing bidirectional string anchors (bd-anchors) [Loukides et al., 2023; Ayad et al., 2025]. - Methods. Inspired by bd-anchors, we introduce the smallest unique substring or SUS-anchor: given a window, this considers all suffixes that do not occur as a substring elsewhere in the window. It then samples the start position of the smallest suffix according to the new anti-lexicographic order that minimizes the first character and maximizes the remaining characters. We give a linear-time and O(w) space streaming algorithm to compute all SUS-anchors of a string. - Results. For alphabet size σ = 4 and k = 1, the parameter-free anti-lexicographic SUS-anchor empirically has density < 1% away from the density lower bound and is at least 4× closer to the lower bound than all other tested schemes. For alphabet size σ = 2, the density is at most 10% above the lower bound, which still improves 2× to 3× the overhead of the random minimizer and is consistently better than the greedy minimizer. Likewise, the anti-lexicographic minimizer performs better than all other schemes apart from the greedy minimizer.
Cite as

Ragnar Groot Koerkamp. The Anti-Lexicographic SUS-Anchor: An Empirically Optimal Selection Scheme. In 26th International Conference on Algorithms for Bioinformatics (WABI 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 390, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp:LIPIcs.WABI.2026.22,
  author =	{Groot Koerkamp, Ragnar},
  title =	{{The Anti-Lexicographic SUS-Anchor: An Empirically Optimal Selection Scheme}},
  booktitle =	{26th International Conference on Algorithms for Bioinformatics (WABI 2026)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-446-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{390},
  editor =	{El-Mabrouk, Nadia and Vandin, Fabio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.22},
  URN =		{urn:nbn:de:0030-drops-275261},
  doi =		{10.4230/LIPIcs.WABI.2026.22},
  annote =	{Keywords: Minimizers, Sampling scheme, Sketching, Maximal suffix, Smallest unique substring}
}
Artifact
Software
DOI: 10.4230/artifacts.27678
RagnarGrootKoerkamp/quickheap

Authors: Johannes Breitling, Ragnar Groot Koerkamp, and Marvin Williams

Abstract
Cite as

Johannes Breitling, Ragnar Groot Koerkamp, Marvin Williams. RagnarGrootKoerkamp/quickheap (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27678,
   title = {{RagnarGrootKoerkamp/quickheap}}, 
   author = {Breitling, Johannes and Groot Koerkamp, Ragnar and Williams, Marvin},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:2cead1c11619177756143a9713ff21207d29fabd;origin=https://github.com/RagnarGrootKoerkamp/quickheap;visit=swh:1:snp:e0266e2ec33db11f26f6e3085d18ce1756621d86;anchor=swh:1:rev:44e0d1819be4eb414f91b55a5a9ebc8fc7f57e49}{\texttt{swh:1:dir:2cead1c11619177756143a9713ff21207d29fabd}} (visited on 2026-08-25)},
   url = {https://github.com/RagnarGrootKoerkamp/quickheap},
   doi = {10.4230/artifacts.27678},
}
Artifact
Software
DOI: 10.4230/artifacts.27680
RagnarGrootKoerkamp/static-hash-sets

Authors: Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders, and Stefan Walzer

Abstract
Cite as

Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders, Stefan Walzer. RagnarGrootKoerkamp/static-hash-sets (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27680,
   title = {{RagnarGrootKoerkamp/static-hash-sets}}, 
   author = {Groot Koerkamp, Ragnar and Hermann, Stefan and Sanders, Peter and Walzer, Stefan},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:d8b8fa726bc8cc741a074c79b7d9bbf0ef0b69e7;origin=https://github.com/RagnarGrootKoerkamp/static-hash-sets;visit=swh:1:snp:df75020c8884cdf5c6ad5b13010f67c098396447;anchor=swh:1:rev:ca72e3fe2ef47c963fc059d98254ccc23ff8b6d5}{\texttt{swh:1:dir:d8b8fa726bc8cc741a074c79b7d9bbf0ef0b69e7}} (visited on 2026-08-25)},
   url = {https://github.com/RagnarGrootKoerkamp/static-hash-sets},
   doi = {10.4230/artifacts.27680},
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.16
SimdQuickHeap: The QuickHeap Reconsidered

Authors: Johannes Breitling, Ragnar Groot Koerkamp, and Marvin Williams

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
Motivation. Priority queues are data structures that maintain a dynamic collection of elements and allow inserting new elements and removing the smallest element. The most widely known and used priority queue is likely the implicit binary heap, even though it has frequent cache misses and is hard to optimize using e.g. SIMD instructions. Contributions. We introduce the SimdQuickHeap, a variant of the QuickHeap that was introduced by Navarro and Paredes in 2010. As suggested by the name, the data structure bears some similarity to QuickSort. We modify the data layout of the original QuickHeap to have all pivots adjacent in memory, with elements between consecutive pivots stored in dedicated buckets. This allows efficient SIMD implementations for both partitioning of buckets and scanning the list of pivots to find the bucket to append newly inserted elements to. The SimdQuickHeap has amortized expected complexity O(log n) per operation, which improves to O((1/W) log n) in non-degenerate cases, where W is the number of words in a SIMD register. In this case, the I/O-complexity is amortized O(1/B) per push and O((1/B) log₂(n/M)) per pop. Results. In synthetic benchmarks, the SimdQuickHeap is 1.2× to 1.7× as fast as the monotone radix heap, the next-best competitor, and 1.4× to 2.8× as fast as the superscalar sample queue, the fastest comparison-based priority queue. The SimdQuickHeap needs around 1.5log₂ n comparisons and log₂ n nanoseconds per pair of push and pop operations. On graph benchmarks with Dijkstra’s shortest path algorithm and Jarník-Prim’s minimum spanning tree algorithm, the SimdQuickHeap is consistently the fastest.
Cite as

Johannes Breitling, Ragnar Groot Koerkamp, and Marvin Williams. SimdQuickHeap: The QuickHeap Reconsidered. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{breitling_et_al:LIPIcs.ESA.2026.16,
  author =	{Breitling, Johannes and Groot Koerkamp, Ragnar and Williams, Marvin},
  title =	{{SimdQuickHeap: The QuickHeap Reconsidered}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.16},
  URN =		{urn:nbn:de:0030-drops-271527},
  doi =		{10.4230/LIPIcs.ESA.2026.16},
  annote =	{Keywords: Heap, SIMD, Priority Queue}
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.20
Non-Minimal k-Perfect Hashing: Tight Lower Bounds and an Application to Fast Static Hash Tables

Authors: Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders, and Stefan Walzer

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
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 α ∈ (0,1] and k ≥ 1. It turns out that combining α < 1 and k ≥ 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 ≈ 8 and ≈ 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× speedup for large n ≥ 30M where a 1-PHF does not fit in cache.
Cite as

Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders, and Stefan Walzer. Non-Minimal k-Perfect Hashing: Tight Lower Bounds and an Application to Fast Static Hash Tables. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 20:1-20:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp_et_al:LIPIcs.ESA.2026.20,
  author =	{Groot Koerkamp, Ragnar and Hermann, Stefan and Sanders, Peter and Walzer, Stefan},
  title =	{{Non-Minimal k-Perfect Hashing: Tight Lower Bounds and an Application to Fast Static Hash Tables}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{20:1--20:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.20},
  URN =		{urn:nbn:de:0030-drops-271565},
  doi =		{10.4230/LIPIcs.ESA.2026.20},
  annote =	{Keywords: Compressed Data Structures, k-Perfect Hashing, Hash Table, Space Lower Bound}
}
Artifact
Software
DOI: 10.4230/artifacts.26761
STPD-index

Authors: Ruben Becker, Davide Cenzato, Travis Gagie, Ragnar Groot Koerkamp, Sung-Hwan Kim, Giovanni Manzini, and Nicola Prezza

Abstract
Cite as

Ruben Becker, Davide Cenzato, Travis Gagie, Ragnar Groot Koerkamp, Sung-Hwan Kim, Giovanni Manzini, Nicola Prezza. STPD-index (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26761,
   title = {{STPD-index}}, 
   author = {Becker, Ruben and Cenzato, Davide and Gagie, Travis and Groot Koerkamp, Ragnar and Kim, Sung-Hwan and Manzini, Giovanni and Prezza, Nicola},
   note = {Software, Funded by the European Union (ERC, REGINDEX, 101039208), swhId: \href{https://archive.softwareheritage.org/swh:1:dir:d4f76a2be744c622f98d403443e3f4507ae9b536;origin=https://github.com/regindex/STPD-index;visit=swh:1:snp:15232c90524e31eb789f2fce1686ae9a23d5f70f;anchor=swh:1:rev:4d8522e4fc1e7bc9781724352e4dcdefb0b8579d}{\texttt{swh:1:dir:d4f76a2be744c622f98d403443e3f4507ae9b536}} (visited on 2026-07-01)},
   url = {https://github.com/regindex/STPD-index},
   doi = {10.4230/artifacts.26761},
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.24
Compressing Suffix Trees by Path Decompositions

Authors: Ruben Becker, Davide Cenzato, Travis Gagie, Ragnar Groot Koerkamp, Sung-Hwan Kim, Giovanni Manzini, and Nicola Prezza

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
The suffix tree is arguably the most fundamental data structure on strings: introduced by Weiner (SWAT 1973) and McCreight (JACM 1976), it allows solving a myriad of computational problems on strings in linear time. Motivated by its large space usage, subsequent research focused first on reducing its size by a constant factor via Suffix Arrays, and later on reaching space proportional to the size of the compressed string. Modern compressed indexes, such as the r-index (Gagie et al., JACM 2020), fit in space proportional to r, the number of runs in the Burrows-Wheeler transform (a strong and universal repetitiveness measure). These advances, however, came with a price: while modern compressed indexes boast optimal bounds in the RAM model, they are often orders of magnitude slower than uncompressed counterparts in practice due to catastrophic cache locality. This reality gap highlights that Big-O complexity in the RAM model has become a misleading predictor of real-world performance, leaving a critical question unanswered: can we design compressed indexes that are efficient in the I/O model of computation? We answer this in the affirmative by introducing a new Suffix Array sampling technique based on particular path decompositions of the suffix tree. We prove that sorting the suffix tree leaves by specific priority functions induces a decomposition where the number of distinct paths (each corresponding to a string suffix) is bounded by r. This allows us to solve indexed pattern matching efficiently in the I/O model using a Suffix Array sample of size at most r, strictly improving upon the (tight) 2r bound of Suffixient Arrays, another recent compressed Suffix Array sampling technique. Experiments confirm that this theoretical I/O efficiency translates to practice in pangenomic applications: our index locates pattern occurrences using less space and orders of magnitude less time than the r-index when performing pattern matching on repetitive DNA collections. Beyond this, our contributions are twofold: (i) unlike Suffixient Arrays, our technique supports most standard suffix tree operations in O(r) space on top of the text while matching the I/O complexity of uncompressed suffix trees; and (ii) we establish a general framework where any valid path decomposition induces a Suffix Array sampling whose size is a new strong repetitiveness measure; we provide a universal mechanism for locating all pattern occurrences for each such path decomposition.
Cite as

Ruben Becker, Davide Cenzato, Travis Gagie, Ragnar Groot Koerkamp, Sung-Hwan Kim, Giovanni Manzini, and Nicola Prezza. Compressing Suffix Trees by Path Decompositions. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 24:1-24:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.ICALP.2026.24,
  author =	{Becker, Ruben and Cenzato, Davide and Gagie, Travis and Groot Koerkamp, Ragnar and Kim, Sung-Hwan and Manzini, Giovanni and Prezza, Nicola},
  title =	{{Compressing Suffix Trees by Path Decompositions}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{24:1--24:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.24},
  URN =		{urn:nbn:de:0030-drops-264139},
  doi =		{10.4230/LIPIcs.ICALP.2026.24},
  annote =	{Keywords: Text indexing, suffix tree, I/O-efficient, Compressed Data Structures}
}
Artifact
Software
DOI: 10.4230/artifacts.25696
RagnarGrootKoerkamp/quadrank

Authors: Ragnar Groot Koerkamp

Abstract
Cite as

Ragnar Groot Koerkamp. RagnarGrootKoerkamp/quadrank (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-25696,
   title = {{RagnarGrootKoerkamp/quadrank}}, 
   author = {Groot Koerkamp, Ragnar},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:83a2ce8d57ab4f246e470f1226e19ecafb51fffe}{\texttt{swh:1:dir:83a2ce8d57ab4f246e470f1226e19ecafb51fffe}} (visited on 2026-06-15)},
   url = {https://github.com/RagnarGrootKoerkamp/quadrank},
   doi = {10.4230/artifacts.25696},
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.20
QuadRank: Engineering a High Throughput Rank

Authors: Ragnar Groot Koerkamp

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Motivation. Given a text, a query rank(q, c) counts the number of occurrences of character c among the first q characters of the text. Space-efficient methods to answer these rank queries form an important building block in many succinct data structures. For example, the FM-index [Ferragina and Manzini, 2000] is a widely used data structure that uses rank queries to locate all occurrences of a pattern in a text. In bioinformatics applications, the goal is usually to process large inputs as fast as possible. Thus, data structures should have high throughput when used with many threads. Contributions. We first survey existing results on rank data structures. For the σ = 2 binary alphabet, we then develop BiRank, which has 3.28% space overhead. BiRank merges the central ideas of two recent papers: (1) we interleave (inline) offsets in each cache line of the underlying bit vector [Laws et al., 2024], reducing cache misses, and (2) these offsets are to the middle of each block so that only half of each needs popcounting [Gottlieb and Reinert, 2025]. In QuadRank (14.4% overhead), we extend these techniques to the σ = 4 (DNA) alphabet. Both data structures typically require only a single cache miss per query, making them highly suitable for high-throughput and memory-bound settings. To enable efficient batch-processing, we support prefetching the cache lines required to answer upcoming queries. Results. BiRank and QuadRank are around 1.5× and 2× faster than similar-overhead methods that do not use interleaving. Prefetching gives an additional 2× speedup, at which point the dual-channel DDR4 RAM bandwidth becomes a hard limit on the total throughput. With prefetching, both methods outperform all other methods apart from SPIDER [Laws et al., 2024] by 2×. When using QuadRank with prefetching in a toy count-only FM-index, QuadFm, this results in a smaller size and up to 4× speedup over Genedex, a state-of-the-art batching FM-index implementation. Conclusion. Optimizing data structures for high throughput, by minimizing cache misses and branch-misses and adding support for prefetching, can result in significant speedups when benchmarks are adjusted accordingly.
Cite as

Ragnar Groot Koerkamp. QuadRank: Engineering a High Throughput Rank. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 20:1-20:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp:LIPIcs.SEA.2026.20,
  author =	{Groot Koerkamp, Ragnar},
  title =	{{QuadRank: Engineering a High Throughput Rank}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{20:1--20:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.20},
  URN =		{urn:nbn:de:0030-drops-260248},
  doi =		{10.4230/LIPIcs.SEA.2026.20},
  annote =	{Keywords: Rank, Succinct Data Structures, Cache Performance, Prefetching}
}
Artifact
Software
DOI: 10.4230/artifacts.23785
rust-seq/simd-minimizers

Authors: Ragnar Groot Koerkamp and Igor Martayan

Abstract
Cite as

Ragnar Groot Koerkamp, Igor Martayan. rust-seq/simd-minimizers (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23785,
   title = {{rust-seq/simd-minimizers}}, 
   author = {Groot Koerkamp, Ragnar and Martayan, Igor},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:d2fbef4c7750f02bc5cb084d0873078fef7f4e22;origin=https://github.com/rust-seq/simd-minimizers;visit=swh:1:snp:7f3e2736cab8ed6759548175a13879f7a95d5bab;anchor=swh:1:rev:078083e8e1f4dbb50ecaf5af8b56a492c72f4bd3}{\texttt{swh:1:dir:d2fbef4c7750f02bc5cb084d0873078fef7f4e22}} (visited on 2025-07-15)},
   url = {https://github.com/rust-seq/simd-minimizers},
   doi = {10.4230/artifacts.23785},
}
Artifact
Software
DOI: 10.4230/artifacts.23786
rust-seq/packed-seq

Authors: Ragnar Groot Koerkamp and Igor Martayan

Abstract
Cite as

Ragnar Groot Koerkamp, Igor Martayan. rust-seq/packed-seq (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23786,
   title = {{rust-seq/packed-seq}}, 
   author = {Groot Koerkamp, Ragnar and Martayan, Igor},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:181f8591389fdf9b941ac6f225a26d2784514787;origin=https://github.com/rust-seq/packed-seq;visit=swh:1:snp:fbb51df438475fe6020067c31d4045f9c1e4d377;anchor=swh:1:rev:e1ec76637d56e1c4bce9f4dc2e3cc32a6dd0b57a}{\texttt{swh:1:dir:181f8591389fdf9b941ac6f225a26d2784514787}} (visited on 2025-07-15)},
   url = {https://github.com/rust-seq/packed-seq},
   doi = {10.4230/artifacts.23786},
}
Artifact
Software
DOI: 10.4230/artifacts.23124
RagnarGrootKoerkamp/PtrHash

Authors: Ragnar Groot Koerkamp

Abstract
Cite as

Ragnar Groot Koerkamp. RagnarGrootKoerkamp/PtrHash (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23124,
   title = {{RagnarGrootKoerkamp/PtrHash}}, 
   author = {Groot Koerkamp, Ragnar},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:5d61696060557f1473ab06eb35d9eaa86d682384;origin=https://github.com/RagnarGrootKoerkamp/PtrHash;visit=swh:1:snp:d758a10ef3720add298a634477960f35038684c0;anchor=swh:1:rev:20499ecf57102589ad513d8a3dafeb9c6a6ed164}{\texttt{swh:1:dir:5d61696060557f1473ab06eb35d9eaa86d682384}} (visited on 2025-07-15)},
   url = {https://github.com/RagnarGrootKoerkamp/PtrHash},
   doi = {10.4230/artifacts.23124},
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.4
U-Index: A Universal Indexing Framework for Matching Long Patterns

Authors: Lorraine A. K. Ayad, Gabriele Fici, Ragnar Groot Koerkamp, Grigorios Loukides, Rob Patro, Giulio Ermanno Pibiri, and Solon P. Pissis

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
Motivation. Text indexing is a fundamental and well-studied problem. Classic solutions to this problem either replace the original text with a compressed representation, e.g., the FM-index and its variants, or keep it uncompressed but attach some redundancy - an index - to accelerate matching, e.g., the suffix array. The former solutions thus retain excellent compressed space, but are practically slow to construct and query. The latter approaches, instead, sacrifice space efficiency but are typically faster; for example, the suffix array takes much more space than the text itself for commonly used alphabets, like ASCII or DNA, but it is very fast to construct and query. Methods. In this paper, we show that efficient text indexing can be achieved using just a small extra space on top of the original text, provided that the query patterns are sufficiently long. More specifically, we develop a new indexing paradigm in which a sketch of a query pattern is first matched against a sketch of the text. Once candidate matches are retrieved, they are verified using the original text. This paradigm is thus universal in the sense that it allows us to use any solution to index the sketched text, like a suffix array, FM-index, or r-index. Results. We explore both the theory and the practice of this universal framework. With an extensive experimental analysis, we show that, surprisingly, universal indexes can be constructed much faster than their unsketched counterparts and take a fraction of the space, as a direct consequence of (i) having a lower bound on the length of patterns and (ii) working in sketch space. Furthermore, these data structures have the potential of retaining or even improving query time, because matching against the sketched text is faster and verifying candidates can be theoretically done in constant time per occurrence (or, in practice, by short and cache-friendly scans of the text). Finally, we discuss some important applications of this novel indexing paradigm to computational biology. We hypothesize that such indexes will be particularly effective when the queries are sufficiently long, and so we demonstrate applications in long-read mapping.
Cite as

Lorraine A. K. Ayad, Gabriele Fici, Ragnar Groot Koerkamp, Grigorios Loukides, Rob Patro, Giulio Ermanno Pibiri, and Solon P. Pissis. U-Index: A Universal Indexing Framework for Matching Long Patterns. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ayad_et_al:LIPIcs.SEA.2025.4,
  author =	{Ayad, Lorraine A. K. and Fici, Gabriele and Groot Koerkamp, Ragnar and Loukides, Grigorios and Patro, Rob and Pibiri, Giulio Ermanno and Pissis, Solon P.},
  title =	{{U-Index: A Universal Indexing Framework for Matching Long Patterns}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.4},
  URN =		{urn:nbn:de:0030-drops-232420},
  doi =		{10.4230/LIPIcs.SEA.2025.4},
  annote =	{Keywords: Text Indexing, Sketching, Minimizers, Hashing}
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.20
SimdMinimizers: Computing Random Minimizers, fast

Authors: Ragnar Groot Koerkamp and Igor Martayan

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
Motivation. Because of the rapidly-growing amount of sequencing data, computing sketches of large textual datasets has become an essential preprocessing task. These sketches are typically much smaller than the input sequences, but preserve sufficient information for downstream analysis. Minimizers are an especially popular sketching technique and used in a wide variety of applications. They sample at least one out of every w consecutive k-mers. As DNA sequencers are getting more accurate, some applications can afford to use a larger w and hence sparser and smaller sketches. And as sketches get smaller, their analysis becomes faster, so the time spent sketching the full-sized input becomes more of a bottleneck. Methods. Our library simd-minimizers implements a random minimizer algorithm using SIMD instructions. It supports both AVX2 and NEON architectures. Its main novelty is two-fold. First, it splits the input into 8 chunks that are streamed over in parallel through all steps of the algorithm. This is enabled by using the completely deterministic two-stacks sliding window minimum algorithm, which seems not to have been used before for finding minimizers. Results. Our library is up to 6.8× faster than a scalar implementation of the rescan method when w = 5 is small, and 3.4× faster for larger w = 19. Computing canonical minimizers is less than 50% slower than computing forward minimizers, and over 15× faster than the existing implementation in the minimizer-iter crate. Our library finds all (canonical) minimizers of a 3.2 Gbp human genome in 5.2 (resp. 6.7) seconds.
Cite as

Ragnar Groot Koerkamp and Igor Martayan. SimdMinimizers: Computing Random Minimizers, fast. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp_et_al:LIPIcs.SEA.2025.20,
  author =	{Groot Koerkamp, Ragnar and Martayan, Igor},
  title =	{{SimdMinimizers: Computing Random Minimizers, fast}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.20},
  URN =		{urn:nbn:de:0030-drops-232581},
  doi =		{10.4230/LIPIcs.SEA.2025.20},
  annote =	{Keywords: Minimizers, Randomized algorithms, Sketching, Hashing}
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.21
PtrHash: Minimal Perfect Hashing at RAM Throughput

Authors: Ragnar Groot Koerkamp

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
Motivation. Given a set K of n keys, a minimal perfect hash function (MPHF) is a collision-free bijective map H_mphf from K to {0, … , n-1}. These functions have uses in databases, search engines, and are used in bioinformatics indexing tools such as Pufferfish (using BBHash), and Piscem (PTHash). PTHash is also used in SSHash, a data structure on k-mers that supports membership queries. PTHash only takes around 5% of the total space of SSHash, and thus, trading slightly more space for faster queries is beneficial. Thus, this work presents a (minimal) perfect hash function that first prioritizes query throughput, while also allowing efficient construction for 10⁹ or more elements using 2.4 bits of memory per key. Contributions. Both PTHash and PHOBIC first map all n keys to n/λ < n buckets. Then, each bucket stores a pilot that controls the final hash value of the keys mapping to it. PtrHash builds on this by using 1) fixed-width (uncompressed) 8-bit pilots, 2) a construction algorithm similar to Cuckoo hashing to find suitable pilot values. Further, it partitions the keys, so that keys in each part map to their own set of slots. PtrHash 3) uses the same number of buckets and slots for each part, with 4) a single remap table to map intermediate positions ≥ n to < n, 5) encoded using per-cacheline Elias-Fano coding. Lastly, 6) PtrHash supports streaming queries, where we use prefetching to answer a stream of multiple queries more efficiently than one-by-one processing. Results. With default parameters, PtrHash takes 2.4 bits per key. On 300 million string keys, PtrHash is as fast or faster to build than other MPHFs at a similar size, and at least 2.1× faster to query. When streaming multiple queries, this improves to 3.3× speedup over the fastest alternative, while also being significantly faster to construct. When using 10⁹ integer keys instead, query times are as low as 12 ns/key when iterating in a for loop, or even down to 8 ns/key when using the streaming approach, just short of the 7.4 ns inverse throughput of random memory accesses.
Cite as

Ragnar Groot Koerkamp. PtrHash: Minimal Perfect Hashing at RAM Throughput. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp:LIPIcs.SEA.2025.21,
  author =	{Groot Koerkamp, Ragnar},
  title =	{{PtrHash: Minimal Perfect Hashing at RAM Throughput}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{21:1--21:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.21},
  URN =		{urn:nbn:de:0030-drops-232597},
  doi =		{10.4230/LIPIcs.SEA.2025.21},
  annote =	{Keywords: Minimal perfect hashing, Compressed Data Structures}
}
Artifact
Software
DOI: 10.4230/artifacts.22525
OCMu64

Authors: Ragnar Groot Koerkamp and Mees de Vries

Abstract
Cite as

Ragnar Groot Koerkamp, Mees de Vries. OCMu64 (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22525,
   title = {{OCMu64}}, 
   author = {Groot Koerkamp, Ragnar and de Vries, Mees},
   note = {Software (visited on 2024-12-05)},
   url = {https://github.com/mjdv/ocmu64},
   doi = {10.4230/artifacts.22525},
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2024.35
PACE Solver Description: OCMu64, a Solver for One-Sided Crossing Minimization

Authors: Ragnar Groot Koerkamp and Mees de Vries

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
Given a bipartite graph (A,B), the one-sided crossing minimization (OCM) problem is to find an ordering of the vertices of B that minimizes the number of edge crossings when drawn in the plane. We introduce the novel strongly fixed, practically fixed, and practically glued reductions that maximally generalize some existing reductions. We apply these in our exact solver OCMu64, that directly uses branch-and-bound on the ordering of the vertices of B and does not depend on ILP or SAT solvers.
Cite as

Ragnar Groot Koerkamp and Mees de Vries. PACE Solver Description: OCMu64, a Solver for One-Sided Crossing Minimization. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 35:1-35:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp_et_al:LIPIcs.IPEC.2024.35,
  author =	{Groot Koerkamp, Ragnar and de Vries, Mees},
  title =	{{PACE Solver Description: OCMu64, a Solver for One-Sided Crossing Minimization}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{35:1--35:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.35},
  URN =		{urn:nbn:de:0030-drops-222616},
  doi =		{10.4230/LIPIcs.IPEC.2024.35},
  annote =	{Keywords: Graph drawing, crossing number, branch and bound}
}
Artifact
Software
DOI: 10.4230/artifacts.22510
RagnarGrootKoerkamp/astar-pairwise-aligner

Authors: Ragnar Groot Koerkamp

Abstract
Cite as

Ragnar Groot Koerkamp. RagnarGrootKoerkamp/astar-pairwise-aligner (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22510,
   title = {{RagnarGrootKoerkamp/astar-pairwise-aligner}}, 
   author = {Groot Koerkamp, Ragnar},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:0da264cc1294d18cb07ee0d76934929e5836e239;origin=https://github.com/RagnarGrootKoerkamp/astar-pairwise-aligner;visit=swh:1:snp:3158598ab43adbfc0661bcb6534fa0cf81397964;anchor=swh:1:rev:d5088352cf2a7474c35b23b046cbda3c4d94c988}{\texttt{swh:1:dir:0da264cc1294d18cb07ee0d76934929e5836e239}} (visited on 2024-11-28)},
   url = {https://github.com/RagnarGrootKoerkamp/astar-pairwise-aligner},
   doi = {10.4230/artifacts.22510},
}
Document
DOI: 10.4230/LIPIcs.WABI.2024.11
The mod-minimizer: A Simple and Efficient Sampling Algorithm for Long k-mers

Authors: Ragnar Groot Koerkamp and Giulio Ermanno Pibiri

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
Motivation. Given a string S, a minimizer scheme is an algorithm defined by a triple (k,w,𝒪) that samples a subset of k-mers (k-long substrings) from a string S. Specifically, it samples the smallest k-mer according to the order 𝒪 from each window of w consecutive k-mers in S. Because consecutive windows can sample the same k-mer, the set of the sampled k-mers is typically much smaller than S. More generally, we consider substring sampling algorithms that respect a window guarantee: at least one k-mer must be sampled from every window of w consecutive k-mers. As a sampled k-mer is uniquely identified by its absolute position in S, we can define the density of a sampling algorithm as the fraction of distinct sampled positions. Good methods have low density which, by respecting the window guarantee, is lower bounded by 1/w. It is however difficult to design a sequence-agnostic algorithm with provably optimal density. In practice, the order 𝒪 is usually implemented using a pseudo-random hash function to obtain the so-called random minimizer. This scheme is simple to implement, very fast to compute even in streaming fashion, and easy to analyze. However, its density is almost a factor of 2 away from the lower bound for large windows. Methods. In this work we introduce mod-sampling, a two-step sampling algorithm to obtain new minimizer schemes. Given a (small) parameter t, the mod-sampling algorithm finds the position p of the smallest t-mer in a window. It then samples the k-mer at position pod w. The lr-minimizer uses t = k-w and the mod-minimizer uses t≡ k (mod w). Results. These new schemes have provably lower density than random minimizers and other schemes when k is large compared to w, while being as fast to compute. Importantly, the mod-minimizer achieves optimal density when k → ∞. Although the mod-minimizer is not the first method to achieve optimal density for large k, its proof of optimality is simpler than previous work. We provide pseudocode for a number of other methods and compare to them. In practice, the mod-minimizer has considerably lower density than the random minimizer and other state-of-the-art methods, like closed syncmers and miniception, when k > w. We plugged the mod-minimizer into SSHash, a k-mer dictionary based on minimizers. For default parameters (w,k) = (11,21), space usage decreases by 15% when indexing the whole human genome (GRCh38), while maintaining its fast query time.
Cite as

Ragnar Groot Koerkamp and Giulio Ermanno Pibiri. The mod-minimizer: A Simple and Efficient Sampling Algorithm for Long k-mers. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp_et_al:LIPIcs.WABI.2024.11,
  author =	{Groot Koerkamp, Ragnar and Pibiri, Giulio Ermanno},
  title =	{{The mod-minimizer: A Simple and Efficient Sampling Algorithm for Long k-mers}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.11},
  URN =		{urn:nbn:de:0030-drops-206552},
  doi =		{10.4230/LIPIcs.WABI.2024.11},
  annote =	{Keywords: Minimizers, Randomized algorithms, Sketching, Hashing}
}
Document
DOI: 10.4230/LIPIcs.WABI.2024.17
A*PA2: Up to 19× Faster Exact Global Alignment

Authors: Ragnar Groot Koerkamp

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
Motivation. Pairwise alignment is at the core of computational biology. Most commonly used exact methods are either based on O(ns) band doubling or O(n+s²) diagonal transition, where n is the sequence length and s the number of errors. However, as the length of sequences has grown, these exact methods are often replaced by approximate methods based on e.g. seed-and-extend and heuristics to bound the computed region. We would like to develop an exact method that matches the performance of these approximate methods. Recently, Astarix introduced the A* shortest path algorithm with the seed heuristic for exact sequence-to-graph alignment. A*PA adapted and improved this for pairwise sequence alignment and achieves near-linear runtime when divergence (error rate) is low, at the cost of being very slow when divergence is high. Methods. We introduce A*PA2, an exact global pairwise aligner with respect to edit distance. The goal of A*PA2 is to unify the near-linear runtime of A*PA on similar sequences with the efficiency of dynamic programming (DP) based methods. Like Edlib, A*PA2 uses Ukkonen’s band doubling in combination with Myers' bitpacking. A*PA2 1) uses large block sizes inspired by Block Aligner, 2) extends this with SIMD (single instruction, multiple data), 3) introduces a new profile for efficient computations, 4) introduces a new optimistic technique for traceback based on diagonal transition, 5) avoids recomputation of states where possible, and 6) applies the heuristics developed in A*PA and improves them using pre-pruning. Results. With the first 4 engineering optimizations, A*PA2-simple has complexity O(ns) and is 6× to 8× faster than Edlib for sequences ≥ 10 kbp. A*PA2-full also includes the heuristic and is often near-linear in practice for sequences with small divergence. The average runtime of A*PA2 is 19× faster than the exact aligners BiWFA and Edlib on >500 kbp long ONT (Oxford Nanopore Technologies) reads of a human genome having 6% divergence on average. On shorter ONT reads of 11% average divergence the speedup is 5.6× (avg. length 11 kbp) and 0.81× (avg. length 800 bp). On all tested datasets, A*PA2 is competitive with or faster than approximate methods.
Cite as

Ragnar Groot Koerkamp. A*PA2: Up to 19× Faster Exact Global Alignment. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp:LIPIcs.WABI.2024.17,
  author =	{Groot Koerkamp, Ragnar},
  title =	{{A*PA2: Up to 19× Faster Exact Global Alignment}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{17:1--17:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.17},
  URN =		{urn:nbn:de:0030-drops-206610},
  doi =		{10.4230/LIPIcs.WABI.2024.17},
  annote =	{Keywords: Edit distance, Pairwise alignment, A*, Shortest path, Dynamic programming}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact