Cache-Oblivious Dynamic Dictionaries with Optimal Update/Query Tradeoff

Gerth Stølting Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono, Stefan Langerman, and J. Ian Munro

In Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1448-1456, 2010.

Abstract

Several existing cache-oblivious dynamic dictionaries achieve O(logB N) (or slightly better O(logB (N/M))) memory transfers per operation, where N is the number of items stored, M is the memory size, and B is the block size, which matches the classic B-tree data structure. One recent structure achieves the same query bound and a sometimes-better amortized update bound of O( 1/BΘ(1/(log log B)2)·logB N + 1/B· log2 N) memory transfers. This paper presents a new data structure, the xDict, implementing predecessor queries in O(1/ε·logB (N/M)) worst-case memory transfers and insertions and deletions in O( 1/(ε B1-ε)·logB (N/M)) amortized memory transfers, for any constant ε with 0 < ε < 1. For example, the xDict achieves subconstant amortized update cost when N = M Bo(B1-ε), whereas the B-tree's Θ(logB (N/M)) is subconstant only when N = o(M B), and the previously obtained Θ( (1/BΘ(1/(log log B)2))logB N + 1/B· log2 N) is subconstant only when N = o( 2\sqrt{B} ). The xDict attains the optimal tradeoff between insertions and queries, even in the broader external-memory model, for the range where inserts cost between Ω((1/B)log1+ε N) and O(1/log3 N) memory transfers.

Copyright notice

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

Online version

soda10.pdf (254 Kb)

DOI

www.siam.org/proceedings/soda/2010/SODA10_117_brodalg.pdf

BIBTEX entry

@inproceedings{soda10,
  author = "Gerth St{\o}lting Brodal and Erik D. Demaine and Jeremy T. Fineman and John Iacono and Stefan Langerman and J. Ian Munro",
  booktitle = "Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms",
  doi = "www.siam.org/proceedings/soda/2010/SODA10_117_brodalg.pdf",
  isbn = "978-0-898716-98-6",
  pages = "1448-1456",
  title = "Cache-Oblivious Dynamic Dictionaries with Optimal Update/Query Tradeoff",
  year = "2010"
}