Cell-Probe Lower Bounds and Complexity-Preserving Reductions for Suffix Array Queries

Abstract

For a text $T$ of length $n$ over an alphabet of size $\sigma$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its inverse suffix array gives the lexicographic rank of the suffix starting at each position. Since the introduction of the FM-index and the compressed suffix array in 2000, both queries have been supported in $O(({\log }_{\sigma }n{)}^{\epsilon })$ time using $O(n\log \sigma )$ bits, for any constant $\epsilon >0$. Yet no nontrivial time-space lower bound for suffix-array queries was known. We give the first such lower bound. Specifically, we show that, in the cell-probe model with $\Theta (\log n)$-bit words, every $S$-bit data structure answering suffix-array queries on binary strings of length at most $n$ has query time $\Omega (\log \log n/\log ((S/n)\log \log n))$. Consequently, every structure using $O(n(\log \log n{)}^{O(1)})$ bits requires $\Omega (\log \log n/\log \log \log n)$ query time, while constant query time requires $\Omega (n{\log }^{\epsilon }n)$ bits for some constant $\epsilon >0$. In particular, no $O(n)$-bit suffix-array representation for binary texts supports constant-time queries, answering the 25-year-old question of Grossi and Vitter. We also give exact complexity-preserving equivalences between suffix-array access and simpler prefix queries on short strings. For every $2\le \sigma \le n$, suffix-array queries are equivalent to prefix-select queries, and inverse-suffix-array queries are equivalent to prefix-special-rank queries. The reductions in both directions preserve all four standard measures up to constant factors: space, query time, preprocessing time, and preprocessing space. Unlike previous reductions, they incur no additive $O(\log \log n)$ query-time term. Thus, the corresponding prefix-query problems capture suffix-array and inverse-suffix-array access without asymptotic loss in any of the four measures.