Lower Bounds for External Memory Dictionaries

Gerth Stølting Brodal and Rolf Fagerberg

In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 546-554, 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 δ 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.

Copyright notice

Copyright © 2003 by the Association for Computer Machinery, Inc., and the Society for Industrial and Applied Mathematics.

Online version

soda03.pdf (180 Kb)

DOI

doi.acm.org/10.1145/644108.644201

Slides

soda03.pdf (190 Kb)

BIBTEX entry

@inproceedings{soda03,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg",
  booktitle = "Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms",
  doi = "doi.acm.org/10.1145/644108.644201",
  isbn = "0-89871-538-5",
  pages = "546-554",
  title = "Lower Bounds for External Memory Dictionaries",
  year = "2003"
}

Other versions