2022/01/26 by Gál, Anna, Miltersen, Peter Bro
#Cell probe model #data structures #lower bounds #time-space tradeoffs
paper · doi:10.4230/dagsemproc.06111.17
In the cell probe model with word size 1 (the bit probe model), a static data structure problem is given by a map f: 0,1n imes 0,1m ightarrow 0,1, where 0,1n is a set of possible data to be stored, 0,1m is a set of possible queries (for natural problems, we have m ll n) and f(x,y) is the answer to question y about data x. A solution is given by a representation phi: 0,1n ightarrow 0,1s and a query algorithm q so that q(phi(x), y) = f(x,y). The time t of the query algorithm is the number of bits it reads in phi(x). In this paper, we consider the case of em succinct representations where s = n + r for some em redundancy r ll 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 geq Omega(n/log n).] 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 property of a coding theoretic flavor. Previously, no omega(m) lower bounds were known on t in the general model for explicit functions, even for very small redundancies. By restricting our attention to em systematic or em index structures phi satisfying phi(x) = x cdot phi^*(x) for some map phi^* (where cdot 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.