License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06111.17
URN: urn:nbn:de:0030-drops-6065
Go to the corresponding Portal

Gál, Anna ; Miltersen, Peter Bro

The Cell Probe Complexity of Succinct Data Structures

06111.GalAnna.Paper.606.pdf (0.3 MB)


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$.
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

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.

BibTeX - Entry

  author =	{G\'{a}l, Anna and Miltersen, Peter Bro},
  title =	{{The Cell Probe Complexity of Succinct Data Structures}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-6065},
  doi =		{10.4230/DagSemProc.06111.17},
  annote =	{Keywords: Cell probe model, data structures, lower bounds, time-space tradeoffs}

Keywords: Cell probe model, data structures, lower bounds, time-space tradeoffs
Collection: 06111 - Complexity of Boolean Functions
Issue Date: 2006
Date of publication: 09.10.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI