Lower bounds for external memory dictionaries

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