Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy

Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton

Abstract

We study the problem of maintaining a dynamic ordered set subject to insertions, deletions, and traversals of k consecutive elements. This problem is trivially solved on a RAM and on a simple two-level memory hierarchy. We explore this traversal problem on more realistic memory models: the cache-oblivious model, which applies to unknown and multi-level memory hierarchies, and sequential-access models, where sequential block transfers are less expensive than random block transfers.
BibTeX
@inproceedings{bender2002scanning,
  author = {Michael A. Bender and Richard Cole and Erik D. Demaine and Martin Farach-Colton},
  title = {{Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy}},
  booktitle = {ESA},
  year = {2002},
  doi = {10.1007/3-540-45749-6\_16},
}
Figure