Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{CacheTradeoff_SODA2010,
  AUTHOR        = {Gerth St{\o}lting Brodal and Erik D. Demaine and
                   Jeremy T. Fineman and John Iacono and Stefan Langerman and
                   J. Ian Munro},
  TITLE         = {Cache-Oblivious Dynamic Dictionaries with Optimal
                   Update/Query Tradeoff},
  BOOKTITLE     = {Proceedings of the 21st Annual ACM-SIAM Symposium on
                   Discrete Algorithms (SODA 2010)},
  bookurl       = {http://www.siam.org/meetings/da10/},
  ADDRESS       = {Austin, Texas},
  MONTH         = {January 17--19},
  YEAR          = 2010,
  PAGES         = {1448--1456},
  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1137/1.9781611973075.117},
  dblp          = {https://dblp.org/rec/conf/soda/BrodalDFILM10},
}

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² 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² 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³ 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]