Scanning and traversing: Maintaining data for traversals in a memory hierarchy

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
EditorsRolf Möhring, Rajeev Raman
PublisherSpringer Verlag
Pages139-150
Number of pages12
ISBN (Electronic)3540441808, 9783540441809
DOIs
StatePublished - 2002
Event10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy
Duration: Sep 17 2002Sep 21 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2461
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th Annual European Symposium on Algorithms, ESA 2002
CountryItaly
CityRome
Period9/17/029/21/02

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Scanning and traversing: Maintaining data for traversals in a memory hierarchy'. Together they form a unique fingerprint.

  • Cite this

    Bender, M. A., Cole, R., Demaine, E. D., & Farach-Colton, M. (2002). Scanning and traversing: Maintaining data for traversals in a memory hierarchy. In R. Möhring, & R. Raman (Eds.), Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings (pp. 139-150). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2461). Springer Verlag. https://doi.org/10.1007/3-540-45749-6_16