8 papers
Hardness of Frequency-Related Queries on Compressed Strings
Rajat De, Dominik Kempa
Compressed indexing aims to support fundamental string queries in space proportional to compressed input size. For grammar compression, a length- string represented…
Wavelet Forests Revisited
Eric Chiu, Dominik Kempa
Rank and select queries are basic operations on sequences, with applications in compressed text indexes and other space-efficient data structures. One of the standard data structur…
Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text
Ankith Reddy Adudodla, Dominik Kempa
Compressed indexing enables powerful queries over massive and repetitive textual datasets using space proportional to the compressed input. While theoretical advances have led to h…
Tight Lower Bounds for Central String Queries in Compressed Space
Dominik Kempa, Tomasz Kociumaka
In this work, we study the limits of compressed data structures, i.e., structures that support various queries on an input text using space proportional to the size of $…
Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
Dominik Kempa, Tomasz Kociumaka
We study the fundamental question of how efficiently suffix array entries can be accessed when the array cannot be stored explicitly. The suffix array of a text of…
Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
Rajat De, Dominik Kempa
Compressed indexing is a powerful technique that enables efficient querying over data stored in compressed form, significantly reducing memory usage and often accelerating computat…