...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Non-Adaptive Data Structure Bounds for Dynamic Predecessor
【24h】

Non-Adaptive Data Structure Bounds for Dynamic Predecessor

机译：动态前身的非自适应数据结构界限

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this work, we continue the examination of the role non-adaptivity plays in maintaining dynamic data structures, initiated by Brody and Larsen. We consider non-adaptive data structures for predecessor search in the w-bit cell probe model. In this problem, the goal is to dynamically maintain a subset T of up to n elements from {1, ..., m}, while supporting insertions, deletions, and a predecessor query Pred(x), which returns the largest element in T that is less than or equal to x. Predecessor search is one of the most well-studied data structure problems. For this problem, using non-adaptivity comes at a steep price. We provide exponential cell probe complexity separations between (i) adaptive and non-adaptive data structures and (ii) non-adaptive and memoryless data structures for predecessor search. A classic data structure of van Emde Boas solves dynamic predecessor search in log(log(m)) probes; this data structure is adaptive. For dynamic data structures which make non-adaptive updates, we show the cell probe complexity is O(log(m)/log(w/log(m))). We also give a nearly-matching Omega(log(m)/log(w)) lower bound. We also give an m/w lower bound for memoryless data structures. Our lower bound technique is tailored to non-adaptive (as opposed to memoryless) updates and might be of independent interest.
机译：在这项工作中，我们将继续研究由Brody和Larsen发起的非适应性在维护动态数据结构中的作用。我们在w位单元探针模型中考虑了非自适应数据结构，用于先前的搜索。在此问题中，目标是动态维护{1，...，m}中最多n个元素的子集T，同时支持插入，删除和前置查询Pred（x），该查询返回其中最大的元素。 T小于或等于x。前身搜索是研究最深入的数据结构问题之一。对于这个问题，使用非适应性的代价很高。我们提供（i）自适应和非自适应数据结构与（ii）非自适应和无内存数据结构之间的指数单元探针复杂度分隔，以进行前驱搜索。 van Emde Boas的经典数据结构解决了log（log（m））探针中的动态前驱搜索;该数据结构是自适应的。对于进行非自适应更新的动态数据结构，我们显示单元探针的复杂度为O（log（m）/ log（w / log（m）））。我们还给出了几乎匹配的Omega（log（m）/ log（w））下限。我们还为无内存数据结构提供了m / w下限。我们的下限技术是针对非自适应（与无记忆）更新量身定制的，可能具有独立利益。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号