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

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^{\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*)log^{1+ε}
*N*) and *O*(1/log^{3} *N*) memory transfers.

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

@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" }