Lower bounds for external memory dictionaries
Lower bounds for external memory dictionaries
复制标题
DOI：
--
复制
发表时间：
2003-01
期刊：
影响因子：
--
通讯作者：
G. Brodal;Rolf Fagerberg
中科院分区：
文献类型：
--
作者：
G. Brodal;Rolf Fagerberg
我们研究基于比较的外存字典在更新时间和查询时间之间的权衡。本文的主要贡献是成员查询和插入的I/O复杂度之间的两个下界权衡：如果有$N^{N/B}$次I/O操作，那么（1）存在一个需要$N/(M\cdot\tilde{O}(\Delta))$次I/O的查询，并且（2）当$\Delta$为$O(B / \log^3 N)$且$N$至少为$M^2$时，存在一个需要$\Omega(\log\Delta\log_2 N)$次I/O的查询。对于这两个下界，我们描述了在广泛的参数范围内给出匹配上界的数据结构，从而表明在这些范围内下界是紧的。
We study trade-offs between the update time and the query time for comparison based external memory dictionaries. The main contributions of this paper are two lower bound trade offs between the I/O complexity of member queries and insertions: If N N/B I/Os, then (1) there exists a query requiring N/(M. ·~O(Δ)) I/Os, and (2) there exists a query requiring Ω(logΔlog2N ~ I/Os when Δ is O(B/log3 N) and N is at least M2. For both lower bound we describe data structures which give matching upper bounds for a wide range of parameters, thereby showing the lower bounds to be tight within these ranges.