143 citations · 504 across the 80 of their papers we have counts for
10 papers · 1 filter
Optimal-Time Dictionary-Compressed Indexes
Anders Roy Christiansen, Mikko Berggren Ettienne, Tomasz Kociumaka +2
We describe the first self-indexes able to count and locate pattern occurrences in optimal time within a space bounded by the size of the most popular dictionary compressors. To ac…
Tunneling on Wheeler Graphs
Jarno Alanko, Travis Gagie, Gonzalo Navarro +1
The Burrows-Wheeler Transform (BWT) is an important technique both in data compression and in the design of compact indexing data structures. It has been generalized from single st…
Relative compression of trajectories
Nieves R. Brisaboa, Travis Gagie, Adrián Gómez-Brandón +2
We present RCT, a new compact data structure to represent trajectories of objects. It is based on a relative compression technique called Relative Lempel-Ziv (RLZ), which compresse…
Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space
Travis Gagie, Gonzalo Navarro, Nicola Prezza
Indexing highly repetitive texts - such as genomic databases, software repositories and versioned text collections - has become an important problem since the turn of the millenniu…
Tree Path Majority Data Structures
Travis Gagie, Meng He, Gonzalo Navarro
We present the first solution to -majorities on tree paths. Given a tree of nodes, each with a label from , and a fixed threshold , such a query gives two nod…
Assembling Omnitigs using Hidden-Order de Bruijn Graphs
Diego Díaz-Domínguez, Djamal Belazzougui, Travis Gagie +3
De novo DNA assembly is a fundamental task in Bioinformatics, and finding Eulerian paths on de Bruijn graphs is one of the dominant approaches to it. In most of the cases, there ma…