9 papers
Patching leaky tunnels in BWTs
Paola Bonizzoni, Davide Cozzi, Travis Gagie +2
We extend Baier's foundationial work on tunnelling Burrows-Wheeler Transforms (BWTs) by showing how something that would be a good tunnel except for a strings that diverge from the…
SimdQuickHeap: The QuickHeap Reconsidered
Johannes Breitling, Ragnar Groot Koerkamp, Marvin Williams
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 use…
Non-minimal k-perfect hashing: Tight lower bounds and an application to fast static hash tables
Ragnar Groot Koerkamp, Stefan Hermann, Peter Sanders +1
A minimal perfect hash function (minimal PHF) is a data structure mapping a static set of keys to bins without collisions. Two natural generalizations are minimal -PHFs…
Revisiting chaining for anchored edit distance
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…
The anti-lexicographic SUS-anchor: a near-optimal k=1 sampling scheme
Ragnar Groot Koerkamp
In recent years, there has been a renewed interest in the search for low density minimizer schemes. These schemes take a window of consecutive -mers, and sample one of them:…
Compressing Suffix Trees by Path Decompositions
Ruben Becker, Davide Cenzato, Travis Gagie +4
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…