论文标题
非自适应数据结构的紧密静态下限
Tight Static Lower Bounds for Non-Adaptive Data Structures
论文作者
论文摘要
在本文中，我们研究了非自适应数据结构的静态细胞探针复杂性，这些静态数据结构将$ n $点的子集维持在$ m = n^{1+ω（1）} $点的宇宙中。当在查询期间选择要访问的内存位置仅取决于查询输入而不取决于内存的内容时，数据结构定义为非自适应。我们证明了$ω（\ log m / \ log（sw / n \ log M））$ static细胞探针探针复杂度的下限，用于解决基本词典问题的非自适应数据结构，其中$ s $表示单元格的数据结构的空间，$ w $是单元格的大小。我们对所有单词尺寸的下限都保持，包括位探针模型（$ W = 1 $），并与Boninger等人的上限相匹配。 [FSTTCS'17]。 我们的结果暗示了具有一轮适应性和至少两轮适应性的字典数据结构之间的急剧二分法。我们表明$ o（1）$或$ o（\ log^{1-ε}（m））$，间接费用词典构造只能在至少两轮适应性的情况下实现。特别是，我们表明许多具有两轮适应性的$ O（1）$词典结构，例如杜鹃哈希（Cuckoo Hashing），在适应性方面都是最佳的。另一方面，非自适应词典必须使用更多的开销。 最后，我们的结果还意味着非自适应前身问题的静态下限。我们的静态下限高于Boninger等人的动态前任问题的$ω（\ log m / \ log w）$的先前，最著名的下限。 [FSTTCS'17]以及RAMAMOORTHY和RAO [CCC'18]在线性空间的自然环境中，每个点都可以适合单个单元格$ W =θ（\ log m）$。此外，我们的结果更强大，因为它们适用于静态设置，这与仅在动态设置中应用的先前下限不同。
In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of $n$ points from a universe consisting of $m=n^{1+Ω(1)}$ points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend only on the query inputs and not on the contents of memory. We prove an $Ω(\log m / \log (sw/n\log m))$ static cell probe complexity lower bound for non-adaptive data structures that solve the fundamental dictionary problem where $s$ denotes the space of the data structure in the number of cells and $w$ is the cell size in bits. Our lower bounds hold for all word sizes including the bit probe model ($w = 1$) and are matched by the upper bounds of Boninger et al. [FSTTCS'17]. Our results imply a sharp dichotomy between dictionary data structures with one round of adaptive and at least two rounds of adaptivity. We show that $O(1)$, or $O(\log^{1-ε}(m))$, overhead dictionary constructions are only achievable with at least two rounds of adaptivity. In particular, we show that many $O(1)$ dictionary constructions with two rounds of adaptivity such as cuckoo hashing are optimal in terms of adaptivity. On the other hand, non-adaptive dictionaries must use significantly more overhead. Finally, our results also imply static lower bounds for the non-adaptive predecessor problem. Our static lower bounds peak higher than the previous, best known lower bounds of $Ω(\log m / \log w)$ for the dynamic predecessor problem by Boninger et al. [FSTTCS'17] and Ramamoorthy and Rao [CCC'18] in the natural setting of linear space $s = Θ(n)$ where each point can fit in a single cell $w = Θ(\log m)$. Furthermore, our results are stronger as they apply to the static setting unlike the previous lower bounds that only applied in the dynamic setting.
