Paper by Erik D. Demaine
- Michael A. Bender, Richard Cole, Erik D. Demaine, and Martin Farach-Colton, “Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy”, in Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), Lecture Notes in Computer Science, volume 2461, Rome, Italy, September 17–21, 2002, pages 139–151.
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.
- This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2461/24610139.pdf.
- The paper is \copyright Springer-Verlag.
- The paper is 12 pages.
- The paper is available in PostScript (176k), gzipped PostScript (69k), and PDF (158k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 2, 2021 by