ALCOMFT-TR-03-80

Anna Gal and Peter Bro Miltersen
The cell probe complexity of succinct data structures
Århus. Work package 4. November 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}ⁿ x {0,1}^m -> {0,1}, where {0,1}ⁿ 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}ⁿ -> {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 Ømega(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.

Postscript file: ALCOMFT-TR-03-80.ps.gz (204 kb).