30 citations · 82 across the 38 of their papers we have counts for
4 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 Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time
Yakov Nekrich
In this paper we describe a dynamic data structure that answers one-dimensional stabbing-max queries in optimal time. Our data structure uses linear space an…
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…
External Memory Orthogonal Range Reporting with Fast Updates
Yakov Nekrich
In this paper we describe data structures for orthogonal range reporting in external memory that support fast update operations. The query costs either match the query costs of the…