**Reference**:- 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. **Abstract**:-
Several existing cache-oblivious dynamic dictionaries achieve
*O*(log_{B}*N*) (or slightly better*O*(log_{B}(*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)}) log_{B}*N*+ (1/*B*) log^{2}*N*) memory transfers. This paper presents a new data structure, the*xDict*, implementing predecessor queries in*O*((1/ε) log_{B}(*N*/*M*)) worst-case memory transfers and insertions and deletions in*O*((1/(ε*B*^{1−ε})) log_{B}(*N*/*M*)) amortized memory transfers, for any constant ε with 0 < ε < 1. For example, the xDict achieves subconstant amortized update cost when*N*=*M**B*^{o(B1−ε)}, whereas the B-tree's Θ(log_{B}(*N*/*M*)) is subconstant only when*N*=*o*(*M**B*), and the previously obtained Θ((1/B^{Θ(1/(log log B)2)}) log_{B}*N*+ (1/*B*) log^{2}*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) lg^{1+ε}*N*) and*O*(1/lg^{3}*N*) memory transfers. **Availability**:- 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.

Last updated February 10, 2020 by Erik Demaine.