Recent content in home on CuriousCoding
Table of Contents Quick introduction A new strategy Inverse operation Some more variants TODO Repeated applications of \(f\) Collisions TODO Consecutive small values \[ \newcommand{\rot}{\mathsf{rot}} \newcommand{\shift}{\mathsf{shift}} \] This is the third post in (by now) a series of 3 posts on NtHash: NtHash1: making it perfect NtHash2: investigating collisions NtHash3: first ideas Previously,…
For a pangenome deduplication tool I’m working on ( pandedup ), I’m using 128-bit hashes as “unique” identifiers of substrings. Sadly, it turns out that gxhash128 (the 128-bit version of gxhash ) has a hash collision between the two strings of length 88 below that only differ in 5 positions, regardless of the value of the seed. Looking at the strings, this clearly…
Table of Contents The Route Prep Day 0 Day 1: Engure river to lake Day 2: Lake + Rinda river to Rinda Day 3: Rinda to middle of Irbe river + walk to ghost town Day 4: Irbe river to the sea Countryside Logistics Boats Water / drinks Food supplies Packing Additions for next time Bird watching Figure 1: An overview of the route we kayaked. (Click to enlarge.)
Previously Link to heading Previously Link to heading Long-read global alignment is just not a problem people have… Link to heading … Sassy: 100bp semi-global alignment Link to heading Takeaway 1: Math yay, Bio nay Link to heading Takeaway 2: Do simple stuff fast Link to heading Approximate String Matching Link to heading Find pattern \(P\) in text \(T\). \(m := |P|\), \(n := |T|\)…
Table of Contents 1 Why should you care? 2 Using Sassy 2.1 The CLI 2.2 Rust library 2.3 Python bindings 2.4 C and R bindings 3 Problem statement: Approximate String Matching 3.1 Overhang: when the pattern extends beyond the read 4 Some background 5 The algorithm 5.1 SIMD 5.2 Sassy2 6 Results 6.1 Sassy1 6.2 Sassy2 6.3 Applications Discuss on reddit . Sassy is a tool for quickly searching short DNA…
FM-index et al.: LF cache-miss per character :( Link to heading I/O-efficient pattern matching using suffix tries Link to heading Suffix trees are in text space and I/O efficient! Suffix trees of repetitive texts are repetitive! “run-length suffix trees” embedded in the text: Suffixient Sets: Depuydt et al. (2023) Suffixient Array: Cenzato et al. (2024) Suffix Tree Path Decomposition:…
Text indexing: Locate all matches of a pattern Link to heading Focus: Locate leftmost match of a pattern Link to heading FM/r-index: cache miss per character Link to heading Suffix trees of repetitive text are repetitive too! Link to heading Suffixient arrays, Cenzato+ Suffix tree: \(O(d + m/B + \mathit{occ})\) I/O complexity Link to heading \(m\): pattern length \(B\): block size \(d\): depth in…
Blackboard: Binary Heap Link to heading Blackboard: QuickHeap Link to heading
Bioinformatics software Link to heading Bioinformatics theory Link to heading Algorithm engineering Link to heading Misc Link to heading
Table of Contents Abstract 1 Introduction 2 Preliminaries 2.1 Minimizer, sampling, and selection schemes 2.2 Bidirectional string anchors 2.3 Maximal suffixes 3 Character-based orders 4 Smallest unique substring anchors 4.1 Properties 4.2 Computing SUS-anchors 5 Results 6 Conclusion \[ \newcommand{\sus}{\mathsf{SUS}} \newcommand{\lcp}{\mathsf{lcp}} \newcommand{\last}{\mathsf{last}} \] A preprint…
Table of Contents 1 Naive 1.1 Compute on-the-fly 1.2 Precompute everything 2 Space lower bounds 3 Sparse Table: \(O(1)\) queries, \(O(n \log_2 n)\) words 4 Segment Tree: \(O(\log n)\) queries, \(O(n)\) words 5 Blocks: \(O(s)\) queries, \(O(n/s \log n)\) words 6 Cartesian Trees: \(O(1)\) queries, \(O(n)\) words 7 Recursive Cartesian Trees: \(O(1)\) queries, \(2n+o(n)\) bits 8 Blackboard \[…
Table of Contents April 2026: The fall of the theorem economy - David Bessis These are some links to interesting posts around the web, with some quick quotes/notes. April 2026: The fall of the theorem economy - David Bessis Link to heading from the moment I conceived of Theorem 0.5, I knew it was true and that proving it would be straightforward. Too long but wow:
Previous slides: Rank & Select , Elias-Fano Link to heading Rank: counting 1 bits 2 levels of blocks of length \(\log^2 n\) and \(\log n\) Select: finding 1 bits 2 levels of blocks with \(\log^2 n\) 1-bits and \(\sqrt{\log n}\) 1-bits. There exist succinct \(o(n)\) space data structures for rank and select. Elias-Fano: efficient encoding of sorted list of integers Split in high and \(\ell\)-bit…
My background Link to heading International co-authors in bioinformatics Link to heading Theory KIT, Venice, Halifax Bioinformatics Venice, Lille, Helsinki, Maryland Practice Birmingham, Utrecht (de-facto PhD “supervisor”) Background Link to heading DNA sequencing is cheap → data grows exponentially High pace of new, fast, heuristic tools Theoretical CS does not match modern hardware…
Previous slides: Bit vectors, Rank & Select Link to heading Bit vector: storing bits Rank: counting 1 bits Select: finding 1 bits Goal: Storing lists of integers Link to heading How do we efficiently store a list of integers \[ 0\leq x_0 \leq x_1 \leq \dots \leq x_{n-1} < U. \] Theorem 1 Lower bound . Using stars and bars , there are \(\binom{U+n-1}{n}\) of choosing \(n\) elements (with…
Last week: Models of computation Link to heading Big-O notation Word RAM model Applications & limitations Today Link to heading Bit vectors storing bits Rank counting 1-bits Select finding 1-bits Engineering Rank making it fast Elias-Fano coding storing integers efficiently Bit vectors Link to heading Definition 1 . A static bit vector is an implicit data structure storing \(n\) bits \(b_0, \dots,…
Organizational matters Link to heading Lectures: In English Monday 14:00 - 15:30 Building 50.34, room 236 Grade: 80% oral exam, 20 minutes 20% programming project Details coming a few weeks Requires registration Materials Link to heading This year’s materials: The course page: ae.iti.kit.edu/english/5028.php Ragnar’s blog: curiouscoding.nl/teaching Lecture notes and/or slides available…
Today Link to heading Why do we care about models? Big-\(O\) notation The complexity of sorting Properties data structures The word RAM model Variations Limitations Motivation Link to heading We want to design fast algorithms, but when is an algorithm fast ? Implement it, and measure the time. Extrapolate experiments to predict performance on larger \(n\). May or may not give understanding. Does…
Tl;dr: if you want to refund your NordVPN payment, go to my.nordaccount.com/billing/billing-history?intent_rf=true . The last part, ?intent_rf=true , is the important bit. (If that doesn’t work, you’ll probably have to go through the full chat-bot flow first, see below. Or maybe they changed the magic bit.) I have a NordVPN subscription since many years. Recently I have been getting…
Table of Contents 1 Problem Statement: Customizable Route Planning (CRP) 2 Contraction Hierarchies (CH) 2.1 Classic Contraction Hierarchies 2.2 Customizable Contraction Hierarchies (CCH) 3 Analogy with trees 4 Shortest Paths in CHs 5 Parents: Faster Shortest Paths in CCHs 6 Input Graph 7 Initial Algorithm 7.1 Permute input 7.2 Chordal Completion and Parents 7.3 Customize 7.4 Query 8 Optimizing…
Table of Contents 1 Deterministic Finite Automaton (DFA) 2 Wheeler-DFA 3 Linear graphs: Prefix array 4 De Bruijn graphs are Wheeler 5 Not all DFAs are Wheeler 6 Locating patterns via binary search 7 Locating patterns via the BOSS table These are some notes on Wheeler DFAs after chatting with Nicola Prezza 1 and others from the RAVEN lab at DSB 2026 in Venice. 1 Deterministic Finite Automaton (DFA)…
My blog: curiouscoding.nl Link to heading Pairwise alignment: finding differences between strings Link to heading Covid – \(\alpha\), December 2020 Link to heading Covid – \(\omicron\), December 2021 Link to heading Pairwise alignment Link to heading Find the mutations between two sequences Dynamic programming Link to heading Dynamic programming Link to heading Dynamic programming Link…
Binary Rank: Problem statement Link to heading Input: a many-GB text \(T = t_0\dots t_{n-1}\) of \(n\) bits. Queries: given \(q\), find \begin{equation*} \newcommand{\rank}{\mathsf{rank}} \rank(q) := \sum_{0\leq i< q} t_i. \end{equation*} \(T = \underline{\texttt{1001001}}\texttt{110010100}\) \(\rank(0) = 0\) \(\rank(7) = 3\) \(\rank(16) = 7\) Why? Occurrences table in FM-index. History Link to…
1 File formats Link to heading This stuff is all insanely confusing. My summary: DEFLATE The ‘original’ compression method. Works in 32kB blocks, and for each stores a small header with the compression mode and optional huffman encoded dictionary. It applies Lempel-Ziv'77 compression of replacing common texts by back-references. It uses a 32kiB context window for this, which may extend…
Table of Contents Abstract 1 Introduction 2 Background 2.1 Further implementations 3 BiRank 3.1 Variants 4 QuadRank 4.1 Variants 5 Results 5.1 BiRank 5.2 QuadRank 6 Conclusion 7 Acknowledgements 8 Code snippets 9 Pairing superblocks 10 Additional results 10.1 Cache misses per query 10.2 Throughput for small inputs 10.3 AMD EPYC evals 11 QuadFm: A Batching FM-index 11.1 Results 12 Further code…
Table of Contents 1 Types of hash tables 2 Metrics 3 Lower bounds 4 Iceberg hashing (2023) 5 IcebergHT (2023) 6 Tight Bounds for Classical Open Addressing (2024) 7 Optimal Non-oblivious Open Addressing (2025) 8 Optimal Bounds for Open Addressing Without Reordering 8.1 Funnel hashing 8.2 Elastic hashing \[ \newcommand{\inv}{^{-1}} \newcommand{\di}{\delta\inv} \newcommand{\poly}{\mathrm{poly}} \]…
Table of Contents 1 Testing 2 Releasing libraries 2.1 Changelog 2.2 cargo release 2.3 crates.io 3 Releasing binaries 3.1 Crates.io 3.2 The pain of AVX2 3.2.1 ensure_simd 3.3 Profile selection 3.4 GitHub 3.5 cargo binstall 3.6 PyPI 3.7 Bioconda 4 Conclusion This post collects the GitHub and BioConda CI configurations I use for maintaining and releasing Sassy. This includes releasing to: crates.io (…
Table of Contents 1 Questions 2 A load of articles/blogs/pages to read 2.1 Wikipedia articles 2.2 More posts 2.3 Notes 2.4 My own RAM 2.5 Continued notes 2.6 Address mapping notation 2.7 Intel spec 2.8 Rank interleaving 2.9 Nontemporal reads/writes 3 reMap: using Performance counters 4 Sudoku 4.1 Step 1: DRAM addressing functions 4.2 Step 2: row/column bits 4.3 Step 3: validation 4.4 Step 4: which…
These are some nice quotes from “The Evolution of Mathematical Software” , Turing Lecture by the 2021 Turing Award winner Jack J. Dongarra, which talks about algorithm and software development in the context of ever improving hardware. a large infrastructure of mathematical libraries […] that must be mainted, ported, and enhanced for many years to come if the value of the application codes…
The Movi 2 paper ( Zakeri et al. 2025 ) builds a fast index on HPRCv2 ( Human Pangenome Reference Consortium 2025 ), a collection of 466 human genomes. This posts collects some statistics on the number of BWT runs (\(r\)) of this dataset, and makes an estimate on the number of unique mutations based on that. Table 1: Number of BWT runs and average run length for a random 3.2Gbp string, a human…
I was listening to an episode of the well there’s your problem podcast about pencil towers ( youtube ), and it had a section on how elevators are a problem because they require a lot of space. So here’s a mathematical version of that. Problem statement Link to heading Given are \(n\) people that need to go to floors \(1, 2, \dots, n\). Elevators have constant acceleration, and must be…
Table of Contents 1 Classification of static data structures 2 Space lower bounds and practical approaches 2.1 Rank 2.2 Rank + Select 2.3 Minimal perfect hash function (MPHF) 2.4 TODO Monotone MPHF 2.5 TODO Order-preserving MPHF 2.6 Static retrieval: Static function with static values 2.7 Updatable retrieval: Static function with mutable values 2.8 Static set (membership) 2.9 Static ordered set…
This is a short note on setting up Doom emacs for very fast typst previews. typst-ts-mode provides typst-ts-watch-mode via C-c C-w , which runs typst watch in the background, as well as typst-ts-preview via C-c C-p which opens the current pdf file. Using zathura as pdf viewer provides live updates. 1 2 3 ;; doom/packages.el ;; typst:…
Table of Contents 1 What’s inside 2 Compile-time feature detection 2.1 Other solutions 3 Rust’s default target-cpu 3.1 cargo build vs cargo install 4 Hardware support 5 Distributing binaries 5.1 GitHub Releases 5.2 Bioconda 5.3 Pypi 6 Open questions Many of my rust crates and binaries building on them use SIMD instructions. Notably: packed-seq , a library for 2-bit encoding DNA ( gh ,…
Table of Contents 1 Problem definitions 2 Optimal solutions 3 Why an overhead is necessary 4 Augmented Retrieval These are some summarizing notes and thoughts on “Static Retrieval Revisited: To Optimality and beyond” by Hu, Kuszmaul, Liang, Yu, Zhang, and Zhou . 1 Problem definitions Link to heading Static Retrieval. Given \(n\) keys \(X\subseteq U\) and \(n\) $v$-bit values \(f(X) \in [2^v]\),…
This is a quick post summarizing the idea of “Singletrack: An Algorithm for Improving Memory Consumption and Performance of Gap-Affine Sequence Alignment” by López-Villellas, Iñiguez, Jiménez-Blanco, Aguado-Puig, Moretó, Alastruey-Benedé, Ibáñez, and Marco-Sola to reduce memory usage of affine-cost alignment by removing the need to store the affine layers of the DP matrix. Affine-cost alignment…
Table of Contents Dormant Long term plans Abandoned Some not-up-to-date lists of ongoing work to keep things organized for myself. Dormant Link to heading Minimizers : publish the anti-lex scheme (→ WABI 26?) continue investigation of greedymini to develop ‘understandable’ equivalent schemes. Find exact optimal schemes for all \(k\equiv 1\pmod w\) lower bound for local schemes Long…
A rating system for theoretical computer scientists. The more logarithms there are (i.e. the more “\(\log\)” before your variables), the higher your reputation will be. No-log theoretical computer scientists are virtually non-existent, as virtually all non-trivial algorithms require use of logarithms. Most are one-log scientists. In the old times (well, I’m young, so these look…
Table of Contents 1 Background Priority queue Binary heap D-ary heaps Other heaps 2 Literature on Quickheaps Optimal incremental sorting Quickheap Randomized quickheaps 3 Bucket-based implementation Data structure Push Pop Partition 4 Results Libraries Datasets Results 5 Conclusion Backlinks : bsky , X , hacker news , lobste.rs A preprint on the SimdQuickHeap ( github:RagnarGrootKoerkamp/QuickHeap…
Table of Contents 1 Minimizing critical sections 2 RabbitFx: chunking 3 Different chunking 4 Experiments 5 Outlook 6 Some helicase benchmarks This is a quick note on some thoughts & experiments on fasta parsing, alongside github:RagnarGrootKoerkamp/fasta-parsing-playground . It’s a common complaint these days that Fasta parsing is slow. A common parser is Needletail ( github ), which builds…
Ragnar {Groot Koerkamp} Link to heading Did IMO & ICPC; currently head-of-jury for NWERC. Some time at Google. Quit and solved all of projecteuler.net (700+) during Covid. Just finished PhD on high throughput bioinformatics @ ETH Zurich. Lots of sequenced DNA that needs processing. Many static datasets, e.g. a 3GB human genome. Revisiting basic algorithms and optimizing them to the limit. Good in…
Minimal Perfect Hash Functions Link to heading A set of \(n\) keys Link to heading A hash function Link to heading A hash function: collisions! Link to heading A hash function: injective / perfect Link to heading A hash function: bijective / minimal & perfect Link to heading Problem statement Link to heading Given a set of \(n\) keys \(K\subseteq \mathbb K\), build a function \(h\) satisfying
For all my projects, feel free to create issues and/or reach out for help in using them. My work is more on algorithm development rather than direct bioinformatics applications, and so I appreciate getting in contact with potential users :) Tools Link to heading Maintained: Deacon by Bede Constantinides: Fast read filtering, building on simd-minimizers. Barbell by Rick Beeloo: Fast and accurate…
Table of Contents GreedyMini Results A first look Comparison with optimal ILP values Large alphabets Analysing GreedyMini at \(w=3\) \(w=3\), \(k=3\) \(w=7\), \(k=3\) \(w=3\), \(k=4\) \(w=3\), \(k=5\) \(w=3\), \(k=6\) \(w=3\), \(k=7\) Looking at fixed \(k=5\) \(k=5\), \(w=4\) \(k=5\), \(w=5\) \(k=5\), \(w=6\) \(k=5\), \(w=7\) \(k=5\), \(w=8\) \(k=5\), \(w=12\) Investigating \(w=5\) \(w=5\),…
What is bio informatics? Link to heading For today: DNA Link to heading Zephyris, CC BY-SA 3.0 Wikipedia Also DNA Link to heading Human chromosomes DNA, according to me Link to heading A C G T 00 01 10 11 Covid Link to heading A virus: SARS-CoV-2, aka COVID-19
Table of Contents Abstract 1 Introduction 1.1 Part 1: Pairwise Alignment 1.2 Part 2: Low Density Minimizers 1.3 Part 3: High Throughput Bioinformatics 2 Discussion 2.1 Pairwise Alignment 2.2 Low Density Minimizers 2.3 High Throughput Bioinformatics 2.4 Propositions This post contains the abstract, introduction, and conclusion of my thesis ( Groot Koerkamp 2025a ). The full PDF is here . Individual…
Table of Contents 1 A Brief History 1.1 A*PA 1.2 A*PA2 1.3 Overview 2 Problem Statement 3 Alignment types 4 Cost Models 4.1 Minimizing Cost versus Maximizing Score 5 The Classic DP Algorithms 6 Linear Memory using Divide and Conquer 7 Dijkstra’s Algorithm and A* 8 Computational Volumes and Band Doubling 9 Diagonal Transition 10 Parallelism 11 LCS and Contours 12 Some Tools 13 Subquadratic…
Table of Contents 1 Theory of Sampling Schemes 1.1 Introduction 1.2 Overview 1.3 Theory of sampling schemes 1.4 Notation 1.5 Types of sampling schemes 1.6 Computing the density 1.7 The density of random minimizers 1.8 Universal hitting sets 1.9 Asymptotic results 1.10 Variants 2 Lower Bounds on Sampling Scheme Density 2.1 Schleimer et al.’s bound 2.2 Marçais et al.’s bound 2.3…
Table of Contents 1 Variants of semi-global alignment 2 Fast text searching 2.1 Skip-cost for overlap alignments 2.2 Results 3 Mapping using A*Map 3.1 Seeding 3.2 Chaining 3.3 Aligning 3.4 A*Map 3.5 Results This is Chapter 5 of my thesis ( Groot Koerkamp 2025 ). Please cite the thesis instead of this post. Summary So far, we have considered only algorithms for global alignment. In this chapter, we…
Table of Contents 1 Introduction 1.1 Overview 2 Optimizing Compute Bound Code: Random Minimizers 2.1 Avoiding Branch Misses 2.2 SIMD: Processing In Parallel 2.3 Instruction Level Parallelism 2.4 Input Format 3 Optimizing Memory Bound Code: Minimal Perfect Hashing 3.1 Using Less Memory 3.2 Reducing Memory Accesses 3.3 Interleaving Memory Accesses 3.4 Batching, Streaming, and Prefetching This is…