Gál, Anna ;
Miltersen, Peter Bro
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 redundancyquery 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 redundancyquery time tradeoff
for the natural data structuring problems of Prefix Sum
and Substring Search.
BibTeX  Entry
@InProceedings{gl_et_al:DSP:2006:606,
author = {Anna G{\'a}l and Peter Bro Miltersen},
title = {The Cell Probe Complexity of Succinct Data Structures},
booktitle = {Complexity of Boolean Functions},
year = {2006},
editor = {Matthias Krause and Pavel Pudl{\'a}k and R{\"u}diger Reischuk and Dieter van Melkebeek},
number = {06111},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2006/606},
annote = {Keywords: Cell probe model, data structures, lower bounds, timespace tradeoffs}
}
Keywords: 

Cell probe model, data structures, lower bounds, timespace tradeoffs 
Seminar: 

06111  Complexity of Boolean Functions

Issue date: 

2006 
Date of publication: 

09.10.2006 