检索结果-内蒙古大学图书馆

The cell probe complexity of succinct data structures

THEORETICAL COMPUTER SCIENCE 2007年第3期379卷 405-417页

作者： Gal, Anna Miltersen, Peter Bro Univ Aarhus Dept Comp Sci Aarhus Denmark Univ Texas Dept Comp Sci Austin TX 78712 USA

We consider time-space tradeoffs for static data structure problems in the cell probe model with word size I (the bit probe model). In this model, the goal is to represent n -bit data with s = n + r bits such that queries (of a certain type) about the data can be answered by reading at most t bits of the representation. Ideally, we would like to keep both s and t small, but there are tradeoffs between the values of s and t that limit the possibilities of keeping both parameters small. 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 (r + 1)t >= 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 properties of a coding theoretic flavor, and obtain (r + 1)t >= Omega(n) for certain problems. Previously, no omega(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) = 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. (c) 2007 Elsevier B.V All rights reserved.

关键词： succinct data structures cell probe complexity polynomial evaluation with preprocessing

来源：评论

学校读者我要写书评

暂无评论

The cell probe complexity of succinct data structures

The cell probe complexity of succinct data structures

引用

30th International Colloquium on Automata, Languages and Programming (ICALP 2003)

作者： Gal, Anna Miltersen, Peter Bro Univ Aarhus Dept Comp Sci Aarhus Denmark Univ Texas Dept Comp Sci Austin TX 78712 USA

ISBN: (纸本)3540404937

关键词： succinct data structures cell probe complexity polynomial evaluation with preprocessing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：