Paper by Erik D. Demaine
- Gerth Stølting Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono, Stefan Langerman, and J. Ian Munro, “Cache-Oblivious Dynamic Dictionaries with Optimal Update/Query Tradeoff”, in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), Austin, Texas, January 17–19, 2010, pages 1448–1456.
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
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 =
whereas the B-tree's Θ(logB (N/M))
is subconstant only when
N = o(M B), and the previously
Θ((1/BΘ(1/(log log B)2))
logB N +
(1/B) log2 N) is subconstant only when
N = o(2√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) lg1+ε N) and
O(1/lg3 N) memory transfers.
- The paper is available in PostScript (526k), gzipped PostScript (127k), and PDF (253k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 18, 2020 by