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
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/606/
|
Go to the corresponding Portal |
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 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.
BibTeX - Entry
@InProceedings{gal_et_al:DagSemProc.06111.17,
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 = {https://drops.dagstuhl.de/opus/volltexte/2006/606},
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 |
