The Cell Probe Complexity of Succinct Data Structures Anna Gál Peter Bro Miltersen December 2003

Abstract:

In the cell probe model with word size 1 (the bit probe model), a static data structure problem is given by a map , where is a set of possible data to be stored, is a set of possible queries (for natural problems, we have ) and is the answer to question about data .

A solution is given by a representation and a query algorithm so that . The time of the query algorithm is the number of bits it reads in .

In this paper, we consider the case of succinct representations where for some redundancy . 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

In particular, for very small redundancies , 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 lower bounds were known on in the general model for explicit functions, even for very small redundancies.

By restricting our attention to systematic or index structures satisfying 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.

Available as PostScript, PDF, DVI.