10 papers · 1 filter
Cell-Probe Lower Bounds and Complexity-Preserving Reductions for Suffix Array Queries
Dominik Kempa, Tomasz Kociumaka
For a text of length over an alphabet of size , its suffix array lists the starting positions of the suffixes of in lexicographic order, and its inverse suffix array…
Constant-Time Inverse Suffix Array Queries in Compact Space and Sublinear-Time Construction of Suffix Array Indexes
Dominik Kempa, Tomasz Kociumaka
For a text with , its suffix array orders the suffix starting positions lexicographically, while its inverse suffix array maps each position to its suf…
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…
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 $T…
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…
Engineering Select Support for Hybrid Bitvectors
Eric Chiu, Dominik Kempa
One of the central problems in the design of compressed data structures is the efficient support for rank and select queries on bitvectors. These two operations form the backbone o…
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…
Word Break on SLP-Compressed Texts
Rajat De, Dominik Kempa
Word Break is a prototypical factorization problem in string processing: Given a word of length and a dictionary of strings,…