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 $f: \{0,1\}^n \times \{0,1\}^m \rightarrow \{0,1\}$, where $\{0,1\}^n$ is a set of possible data to be stored, $\{0,1\}^m$ is a set of possible queries (for natural problems, we have $m « n$) and $f(x,y)$ is the answer to question $y$ about data $x$.

A solution is given by a representation $\phi: \{0,1\}^n \rightarrow \{0,1\}^s$ 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 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 \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 systematic or index structures $\phi$ satisfying $\phi(x) = x · \phi^*(x)$ for some map $\phi^*$ (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.

Last modified: 2004-01-31 by webmaster.