ICS Theory Group

ICS 269, Winter 2002: Theory Seminar

31 Jan 2003:
Lower Bounds for External Memory Dictionaries
Kevin Wortman

We study trade-offs between the update time and the query time for comparison based external memory dictionaries. The main contributions are two lower bound trade-offs between the I/O complexity of member queries and insertions. 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.

(From a SODA 2003 paper by Gerth Brodal and Rolf Fagerberg.)