2026-07-20T05:06:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:606 2024-03-06T11:06:46Z ddc:004 open_access

The Cell Probe Complexity of Succinct Data Structures Gál, Anna Miltersen, Peter Bro Cell probe model data structures lower bounds time-space tradeoffs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anna Gál and Peter Bro Miltersen 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06111.17 urn:nbn:de:0030-drops-6065 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.17 eng https://creativecommons.org/licenses/by/4.0/legalcode