7 papers
Polynomial gaps below linear growth for Kreiss bounded semigroups and operators
Loris Arnold
We prove that every Kreiss bounded -semigroup on a Hilbert space satisfies \[ \|T_t\|\le C(1+t)^{1-\varepsilon_K}, \qquad t\ge0, \] where dep…
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…
Prefix-free parsing for merging big BWTs
Diego Diaz-Dominguez, Travis Gagie, Veronica Guerrini +5
When building Burrows-Wheeler Transforms (BWTs) of truly huge datasets, prefix-free parsing (PFP) can use an unreasonable amount of memory. In this paper we show how if a dataset c…
Depth first representations of -trees
Gabriel Carmona, Giovanni Manzini
The -tree is a compact data structure designed to efficiently store sparse binary matrices by leveraging both sparsity and clustering of nonzero elements. This representation…
Generalization of Repetitiveness Measures for Two-Dimensional Strings
Lorenzo Carfagna, Giovanni Manzini, Giuseppe Romana +2
The problem of detecting and measuring the repetitiveness of one-dimensional strings has been extensively studied in data compression and text indexing. Our understanding of these…
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) consi…