The Cell Probe Complexity of Succinct Data Structures
Anna Gál
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 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
Available as |

Last modified: 2004-01-31 by webmaster.