The Cell Probe Complexity of Succinct Data Structures

Anna Gal; Peter Bro Miltersen

doi:10.1007/3-540-45061-0_28

The Cell Probe Complexity of Succinct Data Structures

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning

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 \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

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 satisfying (x)=x dot operator ^*(x) for some map ^* (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.

Originalsprog	Engelsk
Titel	Automata, Languages and Programming : 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 - July 4, 2003 Proceedings
Redaktører	Jos C.M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Wöeginger
Antal sider	12
Forlag	Springer
Publikationsdato	2003
Sider	442-453
ISBN (Trykt)	9783540405436
ISBN (Elektronisk)	3540405437
DOI	https://doi.org/10.1007/3-540-45061-0_28
Status	Udgivet - 2003
Begivenhed	International Colloquium on Automata, Languages and Programming. ICALP 2003 - Eindhoven, Holland Varighed: 30 jun. 2003 → 4 jul. 2003 Konferencens nummer: 30

Konference

Konference	International Colloquium on Automata, Languages and Programming. ICALP 2003
Nummer	30
Land/Område	Holland
By	Eindhoven
Periode	30/06/2003 → 04/07/2003

Navn	Lecture Notes in Computer Science
Vol/bind	2719
ISSN	0302-9743

Adgang til dokumentet

10.1007/3-540-45061-0_28

Citationsformater

Gal, Anna ; Miltersen, Peter Bro. / The Cell Probe Complexity of Succinct Data Structures. Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 - July 4, 2003 Proceedings. red. / Jos C.M. Baeten ; Jan Karel Lenstra ; Joachim Parrow ; Gerhard J. Wöeginger. Springer, 2003. s. 442-453 (Lecture Notes in Computer Science, Bind 2719).

@inproceedings{b7370660983b11dabee902004c4f4f50,

title = "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 , where is a set of possible data to be stored, is a set of possible queries (for natural problems, we have ) and is the answer to question about data . A solution is given by a representation and a query algorithm so that . The time of the query algorithm is the number of bits it reads in . In this paper, we consider the case of succinct representations where for some redundancy . 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 In particular, for very small redundancies , 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 lower bounds were known on in the general model for explicit functions, even for very small redundancies. By restricting our attention to systematic or index structures satisfying for some map (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 satisfying (x)=x*(x) for some map * (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.",

keywords = "Succinct data structures, Cell probe complexity, Polynomial evaluation with preprocessing",

author = "Anna Gal and Miltersen, {Peter Bro}",

year = "2003",

doi = "10.1007/3-540-45061-0_28",

language = "English",

isbn = "9783540405436",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "442--453",

editor = "Baeten, {Jos C.M.} and Lenstra, {Jan Karel} and Joachim Parrow and W{\"o}eginger, {Gerhard J.}",

booktitle = "Automata, Languages and Programming",

address = "Netherlands",

note = "International Colloquium on Automata, Languages and Programming. ICALP 2003 ; Conference date: 30-06-2003 Through 04-07-2003",

}

Gal, A & Miltersen, PB 2003, The Cell Probe Complexity of Succinct Data Structures. i JCM Baeten, JK Lenstra, J Parrow & GJ Wöeginger (red), Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 - July 4, 2003 Proceedings. Springer, Lecture Notes in Computer Science, bind 2719, s. 442-453, International Colloquium on Automata, Languages and Programming. ICALP 2003, Eindhoven, Holland, 30/06/2003. https://doi.org/10.1007/3-540-45061-0_28

The Cell Probe Complexity of Succinct Data Structures. / Gal, Anna; Miltersen, Peter Bro.
Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 - July 4, 2003 Proceedings. red. / Jos C.M. Baeten; Jan Karel Lenstra; Joachim Parrow; Gerhard J. Wöeginger. Springer, 2003. s. 442-453 (Lecture Notes in Computer Science, Bind 2719).

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning

TY - GEN

T1 - The Cell Probe Complexity of Succinct Data Structures

AU - Gal, Anna

AU - Miltersen, Peter Bro

N1 - Conference code: 30

PY - 2003

Y1 - 2003

N2 - In the cell probe model with word size 1 (the bit probe model), a static data structure problem is given by a map , where is a set of possible data to be stored, is a set of possible queries (for natural problems, we have ) and is the answer to question about data . A solution is given by a representation and a query algorithm so that . The time of the query algorithm is the number of bits it reads in . In this paper, we consider the case of succinct representations where for some redundancy . 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 In particular, for very small redundancies , 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 lower bounds were known on in the general model for explicit functions, even for very small redundancies. By restricting our attention to systematic or index structures satisfying for some map (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 satisfying (x)=x*(x) for some map * (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.

AB - In the cell probe model with word size 1 (the bit probe model), a static data structure problem is given by a map , where is a set of possible data to be stored, is a set of possible queries (for natural problems, we have ) and is the answer to question about data . A solution is given by a representation and a query algorithm so that . The time of the query algorithm is the number of bits it reads in . In this paper, we consider the case of succinct representations where for some redundancy . 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 In particular, for very small redundancies , 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 lower bounds were known on in the general model for explicit functions, even for very small redundancies. By restricting our attention to systematic or index structures satisfying for some map (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 satisfying (x)=x*(x) for some map * (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.

KW - Succinct data structures

KW - Cell probe complexity

KW - Polynomial evaluation with preprocessing

U2 - 10.1007/3-540-45061-0_28

DO - 10.1007/3-540-45061-0_28

M3 - Article in proceedings

SN - 9783540405436

T3 - Lecture Notes in Computer Science

SP - 442

EP - 453

BT - Automata, Languages and Programming

A2 - Baeten, Jos C.M.

A2 - Lenstra, Jan Karel

A2 - Parrow, Joachim

A2 - Wöeginger, Gerhard J.

PB - Springer

T2 - International Colloquium on Automata, Languages and Programming. ICALP 2003

Y2 - 30 June 2003 through 4 July 2003

ER -

Gal A, Miltersen PB. The Cell Probe Complexity of Succinct Data Structures. I Baeten JCM, Lenstra JK, Parrow J, Wöeginger GJ, red., Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 - July 4, 2003 Proceedings. Springer. 2003. s. 442-453. (Lecture Notes in Computer Science, Bind 2719). doi: 10.1007/3-540-45061-0_28

The Cell Probe Complexity of Succinct Data Structures

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater