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

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

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

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

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.

Original language | English |
---|---|

Title of host publication | Automata, Languages and Programming : 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 - July 4, 2003 Proceedings |

Editors | Jos C.M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Wöeginger |

Number of pages | 12 |

Publisher | Springer |

Publication year | 2003 |

Pages | 442-453 |

ISBN (print) | 9783540405436 |

ISBN (Electronic) | 3540405437 |

DOIs | |

Publication status | Published - 2003 |

Event | International Colloquium on Automata, Languages and Programming. ICALP 2003 - Eindhoven, Netherlands Duration: 30 Jun 2003 → 4 Jul 2003 Conference number: 30 |

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

Nummer | 30 |

Land | Netherlands |

By | Eindhoven |

Periode | 30/06/2003 → 04/07/2003 |

Series | Lecture Notes in Computer Science |
---|---|

Volume | 2719 |

ISSN | 0302-9743 |

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

See relations at Aarhus University Citationformats

ID: 281797