The cell probe complexity of succinct data structures

AbstractWe consider time-space tradeoffs for static data structure problems in the cell probe model with word size 1 (the bit probe model). In this model, the goal is to represent n-bit data with s=n+r bits such that queries (of a certain type) about the data can be answered by reading at most t bits of the representation. Ideally, we would like to keep both s and t small, but there are tradeoffs between the values of s and t that limit the possibilities of keeping both parameters small.In this paper, we consider the case of succinct representations, where s=n+r for some redundancy r≪n. For a Boolean version of the problem of polynomial evaluation with preprocessing of coefficients, we show a lower bound on the redundancy–query time tradeoff of the form (r+1)t≥Ω(n/logn). In particular, for very small redundancies r, we get an almost optimal lower bound stating that the query algorithm has to inspect almost the entire data structure (up to a logarithmic factor). We show similar lower bounds for problems satisfying a certain combinatorial properties of a coding theoretic flavor, and obtain (r+1)t≥Ω(n) for certain problems. Previously, no ω(m) lower bounds were known on t in the general model for explicit Boolean problems, even for very small redundancies.By restricting our attention to systematic or index structures ϕ satisfying ϕ(x)=x⋅ϕ∗(x) for some map ϕ∗ (where ⋅ denotes concatenation), we show similar lower bounds on the redundancy–query time tradeoff for the natural data structuring problems of Prefix Sum and Substring Search