Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy
Lists
Only you see this
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},
}