Tight Lower Bounds for Central String Queries in Compressed Space

In this work, we study the limits of compressed data structures, i.e., structures that support various queries on an input text T ∈ Σⁿ while using space proportional to the size of T in compressed form. Nearly all fundamental queries can currently be efficiently supported in O(δ(T) log^O(1) n) space, where δ(T) is the substring complexity—a strong compressibility measure that lower-bounds the optimal space required to represent the text [Kociumaka, Navarro, Prezza; IEEE Trans. Inf. Theory 2023]. In contrast, the optimal query time for compressed data structures has been characterized only for the basic random access problem. We address this gap by developing tight lower bounds for nearly all other fundamental string-processing queries. First, we prove that suffix array (SA), inverse suffix array (SA⁻¹), longest common prefix (LCP) array, and longest common extension (LCE) queries all require Ω( log n/log log n) time within O(δ(T) log^O(1) n) space, matching known upper bounds. We further show that other common queries, currently supported in O(log log n) time and O(δ(T) log^O(1) n) space—including the Burrows–Wheeler Transform (BWT), permuted longest common prefix (PLCP) array, Last-to-First (LF), inverse Last-to-First (LF⁻¹), lexicographic predecessor (Φ), and inverse lexicographic predecessor (Φ⁻¹) queries—all require Ω(log log n) time, yielding another set of tight bounds. Our lower bounds hold even for texts over a binary alphabet. This work establishes a clean dichotomy: the optimal time complexity to support central string queries in compressed space is either Θ(log n/log log n) or Θ(log log n). This completes the theoretical foundation of compressed indexing, closing a crucial gap between upper and lower bounds and providing a clear target for future data structures: seeking either the optimal time in the smallest space or the fastest time in the optimal space, both of which are now known for central string queries.