Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs
Gerth Stølting Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono, Stefan Langerman, J. Ian Munro · 2010
Several existing cache-oblivious dynamic dictionaries achieve O(logB N) (or slightly better 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 memory transfers. This paper presents a new data structure, the xDict, implementing predecessor queries in worst-case memory transfers and insertions and deletions in amortized memory transfers, for any constant ε with 0 < ε < 1. For example, the xDict achieves subconstant amortized update cost when N = M B°(B1−∊), whereas the B-tree's is subconstant only when N = o(MB), and the previously obtained is subconstant only when . The xDict attains the optimal tradeoff between insertions and queries, even in the broader external-memory model, for the range where inserts cost between and O(1/lg3 N) memory transfers.