Lower Bounds for External Memory Dictionaries

Gerth Stølting Brodal and Rolf Fagerberg

Technical Report, ALCOMFT-TR-03-75, ALCOM-FT, 13 pages, November 2003.


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 δ· N/B I/Os, then (1) there exists a query requiring N/(M·(M/B)O(δ)) I/Os, and (2) there exists a query requiring Ω(logδ log2 N (N/M)) I/Os when δ is O(B/log3 N) and N is at least M2. 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.

Online version

alcomft-tr-03-75.pdf (181 Kb)

BIBTEX entry

  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg",
  institution = "ALCOM-FT",
  month = "November",
  number = "ALCOMFT-TR-03-75",
  pages = "13",
  title = "Lower Bounds for External Memory Dictionaries",
  year = "2003"