You are here: » The Cell Probe Complexity of Succinct Data Structures

The Cell Probe Complexity of Succinct Data Structures

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research

DOI

  • Anna Gal, Department of Computer Science, University of Texas at Austin, Austin, TX 78712-1188, United States
  • Peter Bro Miltersen
  • Department of Computer Science
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 \times \{0,1\}^m \rightarrow \{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 « 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 \rightarrow \{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

\begin{displaymath}(r+1) t \geq \Omega(n/\log n).\end{displaymath}

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.

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≥Ω(n/logn).
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 properties of a coding theoretic flavor, and obtain (r+1)t≥Ω(n) for certain problems. Previously, no ω(m) lower bounds were known on t in the general model for explicit Boolean problems, even for very small redundancies.

By restricting our attention to systematic or index structures phi satisfying phi(x)=xdot operatorphi*(x) for some map phi* (where dot operator 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.

Original languageEnglish
Title of host publicationAutomata, Languages and Programming : 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 - July 4, 2003 Proceedings
EditorsJos C.M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Wöeginger
Number of pages12
PublisherSpringer
Publication year2003
Pages442-453
ISBN (print)9783540405436
ISBN (Electronic)3540405437
DOIs
Publication statusPublished - 2003
EventInternational Colloquium on Automata, Languages and Programming. ICALP 2003 - Eindhoven, Netherlands
Duration: 30 Jun 2003 → 4 Jul 2003
Conference number: 30

Conference

ConferenceInternational Colloquium on Automata, Languages and Programming. ICALP 2003
Nummer30
LandNetherlands
ByEindhoven
Periode30/06/2003 → 04/07/2003
SeriesLecture Notes in Computer Science
Volume2719
ISSN0302-9743

    Research areas

  • Succinct data structures, Cell probe complexity, Polynomial evaluation with preprocessing

See relations at Aarhus University Citationformats

ID: 281797