Paper by Erik D. Demaine

Reference:
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.

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.

Comments:
This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2461/24610139.pdf.

Copyright:
The paper is \copyright Springer-Verlag.

Length:
The paper is 12 pages.

Availability:
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 BibTeX file.
Last updated March 12, 2024 by Erik Demaine.