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 July 23, 2024 by
Erik Demaine.