143 citations · 479 across the 107 of their papers we have counts for
9 papers · 1 filter
Searching and Indexing Genomic Databases via Kernelization
Travis Gagie, Simon J. Puglisi
The rapid advance of DNA sequencing technologies has yielded databases of thousands of genomes. To search and index these databases effectively, it is important that we take advant…
Queries on LZ-Bounded Encodings
Djamal Belazzougui, Travis Gagie, Paweł Gawrychowski +4
We describe a data structure that stores a string in space similar to that of its Lempel-Ziv encoding and efficiently supports access, rank and select queries. These queries ar…
Variable-Order de Bruijn Graphs
Christina Boucher, Alex Bowe, Travis Gagie +2
The de Bruijn graph of a set of strings is a key data structure in genome assembly that represents overlaps between all the -length substrings of . Construction and…
Faster Compressed Quadtrees
Guillermo de Bernardo, Travis Gagie, Susana Ladra +2
Real-world point sets tend to be clustered, so using a machine word for each point is wasteful. In this paper we first show how a compact representation of quadtrees using $\Oh{1}$…
Efficient and Compact Representations of Prefix Codes
Travis Gagie, Gonzalo Navarro, Yakov Nekrich +1
Most of the attention in statistical compression is given to the space used by the compressed sequence, a problem completely solved with optimal prefix codes. However, in many appl…
Document Counting in Practice
Travis Gagie, Aleksi Hartikainen, Juha Kärkkäinen +3
We address the problem of counting the number of strings in a collection where a given pattern appears, which has applications in information retrieval and data mining. Existing so…