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 M insertions perform at most Δ · 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/log3N) 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.
展开▼
机译：我们研究了更新时间和查询时间之间的权衡，以用于基于比较的外部内存字典。本文的主要贡献是成员查询和插入的I / O复杂度之间的两个下限权衡：如果N N / B I / O s ，则（1）存在一个查询，要求N /（M。·〜 O （Δ） ）I / O s ，并且（2）存在一个查询，要求Ω（log Δlog 2 N 〜I / O当Δ是 O （ B / log 3 N ）和 N 至少为 M 2 。对于这两个下限，我们描述了数据结构，这些结构给出了适用于各种参数的匹配上限，从而显示了下限在这些范围内，边界一定要严格。
展开▼
