65 citations · 333 across the 44 of their papers we have counts for
6 papers · 2 filters
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…
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…
Rank, select and access in grammar-compressed strings
Djamal Belazzougui, Simon J. Puglisi, Yasuo Tabei
Given a string of length on a fixed alphabet of symbols, a grammar compressor produces a context-free grammar of size that generates and only . In this p…
Document Retrieval on Repetitive Collections
Gonzalo Navarro, Simon J. Puglisi, Jouni Sirén
Document retrieval aims at finding the most important documents where a pattern appears in a collection of strings. Traditional pattern-matching techniques yield brute-force docume…