Lower bounds for external memory dictionaries

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 \ (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.