1 citations · 1 across the 8 of their papers we have counts for
9 papers
Taxonomic Classification with Tag Arrays
Travis Gagie, Gonzalo Navarro
Taxonomic classifiers based on exact matches differ in which matches they use and in how each match splits its credit among the taxa containing it: Kraken~2 gives a -mer's credi…
Compressed Set Representations based on Set Difference
Travis Gagie, Meng He, Gonzalo Navarro
We introduce a compressed representation of sets of sets that exploits how similar they are to each other. Our representation supports access, membership, predecessor and successor…
Fast and Small Subsampled R-indexes
Dustin Cobas, Travis Gagie, Gonzalo Navarro
The -index represented a breakthrough in compressed indexing of repetitive text collections, outperforming its alternatives by orders of magnitude in query time. Its space usage…
Faster run-length compressed suffix arrays
Nathaniel K. Brown, Travis Gagie, Giovanni Manzini +2
We first review how we can store a run-length compressed suffix array (RLCSA) for a text of length over an alphabet of size whose Burrows-Wheeler Transform (BWT) consis…
Iterated Straight-Line Programs
Gonzalo Navarro, Cristian Urbina
We explore an extension to straight-line programs (SLPs) that outperforms, for some text families, the measure based on substring complexity, a lower bound for most measures an…
Taxonomic classification with maximal exact matches in KATKA kernels and minimizer digests
Dominika Draesslerová, Omar Ahmed, Travis Gagie +4
For taxonomic classification, we are asked to index the genomes in a phylogenetic tree such that later, given a DNA read, we can quickly choose a small subtree likely to contain th…
Faster Maximal Exact Matches with Lazy LCP Evaluation
Adrián Goga, Lore Depuydt, Nathaniel K. Brown +3
MONI (Rossi et al., {\it JCB} 2022) is a BWT-based compressed index for computing the matching statistics and maximal exact matches (MEMs) of a pattern (usually a DNA read) with re…
Space-efficient conversions from SLPs
Travis Gagie, Adrián Goga, Artur Jeż +1
We give algorithms that, given a straight-line program (SLP) with rules that generates (only) a text , builds within space the Lempel-Ziv (LZ) parse of (of…
Better Space Bounds for Parameterized Range Majority and Minority
Djamal Belazzougui, Travis Gagie, Gonzalo Navarro
Karpinski and Nekrich (2008) introduced the problem of parameterized range majority, which asks to preprocess a string of length such that, given the endpoints of a range, one…