65 citations · 333 across the 44 of their papers we have counts for
6 papers · 1 filter
A Compressed Self-Index for Genomic Databases
Travis Gagie, Juha Kärkkäinen, Yakov Nekrich +1
Advances in DNA sequencing technology will soon result in databases of thousands of genomes. Within a species, individuals' genomes are almost exact copies of each other; e.g., any…
A Faster Grammar-Based Self-Index
Travis Gagie, Paweł Gawrychowski, Juha Kärkkäinen +2
To store and search genomic databases efficiently, researchers have recently started building compressed self-indexes based on grammars. In this paper we show how, given a straight…
Faster Approximate Pattern Matching in Compressed Repetitive Texts
Travis Gagie, Paweł Gawrychowski, Christopher Hoobin +1
Motivated by the imminent growth of massive, highly redundant genomic databases, we study the problem of compressing a string database while simultaneously supporting fast random a…
Reference Sequence Construction for Relative Compression of Genomes
Shanika Kuruppu, Simon Puglisi, Justin Zobel
Relative compression, where a set of similar strings are compressed with respect to a reference string, is a very effective method of compressing DNA datasets containing multiple s…
Relative Lempel-Ziv Factorization for Efficient Storage and Retrieval of Web Collections
Christopher Hoobin, Simon J. Puglisi, Justin Zobel
Compression techniques that support fast random access are a core component of any information system. Current state-of-the-art methods group documents into fixed-sized blocks and…
Fixed Block Compression Boosting in FM-Indexes
Juha Kärkkäinen, Simon J. Puglisi
A compressed full-text self-index occupies space close to that of the compressed text and simultaneously allows fast pattern matching and random access to the underlying text. Amon…