Cache-oblivious dynamic dictionaries with update/query tradeoffs
Cache-oblivious dynamic dictionaries with update/query tradeoffs
复制标题
DOI：
10.1137/1.9781611973075.117
复制
发表时间：
2010-01
期刊：
影响因子：
--
通讯作者：
G. Brodal;E. Demaine;Jeremy T. Fineman;J. Iacono;S. Langerman;J. Munro
中科院分区：
文献类型：
--
作者：
G. Brodal;E. Demaine;Jeremy T. Fineman;J. Iacono;S. Langerman;J. Munro
几种现有的缓存无关动态字典每次操作实现$O(\log_{B}N)$（或者稍优的$O(\log_{B}\frac{N}{M})$）次内存传输，其中$N$是存储的元素数量，$M$是内存大小，$B$是块大小，这与经典的B树数据结构相匹配。一种近期的结构实现了相同的查询界，以及有时更优的平摊更新界为$O(\frac{1}{B^{\Theta(\frac{1}{\log\log B})^{2}}}\log_{B}N + \frac{1}{B}\log^{2}N)$次内存传输。本文提出一种新的数据结构，即xDict，它在最坏情况下以$O(\frac{1}{\varepsilon}\log_{B}\frac{N}{M})$次内存传输实现前驱查询，并且以$O(\frac{1}{\varepsilon}B^{1 - \varepsilon}\log_{B}\frac{N}{M})$次平摊内存传输实现插入和删除操作，对于任何满足$0 < \varepsilon < 1$的常数$\varepsilon$，只要$N = M^{B^{o(B^{1 - \varepsilon})}}$，而B树的$\Theta(\log_{B}\frac{N}{M})$仅当$N = o(MB)$时才是次常数，并且先前得到的$\Theta(\frac{1}{B^{\Theta(\frac{1}{(\log\log B)^{2}})}\log_{B}N + \frac{1}{B}\log^{2}N)$仅当$N = o(2^{\sqrt{B}})$时才是次常数。xDict在插入和查询之间实现了最优权衡，即使在更广泛的外部内存模型中，对于插入操作的内存传输成本在$\Omega(\frac{1}{B}\lg^{1 + \varepsilon}N)$和$O(\frac{1}{\lg^{3}N})$之间的范围也是如此。
Several existing cache-oblivious dynamic dictionaries achieve O(logB N) (or slightly better O(logB N/M)) memory transfers per operation, where N is the number of items stored, M is the memory size, and B is the block size, which matches the classic B-tree data structure. One recent structure achieves the same query bound and a sometimes-better amortized update bound of O(1/BΘ(1/log log B)2) logB N + 1/B log2 N) memory trans-fers. This paper presents a new data structure, the xDict, implementing predecessor queries in O(1/ε log B N/M) worst-case memory transfers and insertions and deletions in O(1/εB1-ε logB N/M) amortized memory transfers, for any constant ε with 0 N = M Bo(B1-ε), whereas the B-tree's Θ(logB N/M) is subconstant only when N = o(MB), and the previously obtained Θ(1/BΘ(1/(log log B)2) logB N + 1/B log2 N) is subconstant only when N = o(2√B). The xDict attains the optimal tradeoff between insertions and queries, even in the broader external-memory model, for the range where inserts cost between Ω(1/B lg1+ε N) and O(1/lg3 N) memory transfers.