Lower bounds for external memory dictionaries
Gerth Stølting Brodal, Rolf Fagerberg · 2003
We study trade-offs between the update time and the query time for comparisonbased 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 ffi * N/B I/Os, then (1) there exists a query requiring N/(M * ( MB)O(ffi)) I/Os, and (2) there exists a query requiring \\Omega (logffi log2 N NM) I/Os when ffi is O(B / log3 N) and N is at least M 2. For both lower bounds we describe data structureswhich give matching upper bounds for a wide range of parameters, thereby showing the lower bounds to be tight within these ranges.