The Cell Probe Complexity of Succinct Data Structures

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 	imes {0,1}^m 
ightarrow {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 ll 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 
ightarrow {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 {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.