ALCOMFT-TR-03-75

Gerth Stølting Brodal and Rolf Fagerberg
Lower Bounds for External Memory Dictionaries
Århus. Work packages 1 and 4. November 2003.

Abstract: 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 \delta· N/B I/Os, then (1) there exists a query requiring N/(M·((M)/(B))^O(\delta)) I/Os, and (2) there exists a query requiring Omega(log_{\delta log² N} (N)/(M)) I/Os when \delta is O(B/log³ N) and N is at least M². For both lower bounds 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.

Postscript file: ALCOMFT-TR-03-75.ps.gz (178 kb).