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.

BibTeX

@InProceedings{Traversals_ESA2002,
  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     = {Proceedings of the 10th Annual European Symposium on
                   Algorithms (ESA 2002)},
  bookurl       = {http://www.dis.uniroma1.it/~algo02/esa02/},
  SERIES        = {Lecture Notes in Computer Science},
  SERIESURL     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 2461,
  ADDRESS       = {Rome, Italy},
  MONTH         = {September 17--21},
  YEAR          = 2002,
  PAGES         = {139--151},

  copyright     = {The paper is \copyright Springer-Verlag.},
  length        = {12 pages},
  doi           = {https://dx.doi.org/10.1007/3-540-45749-6_16},
  dblp          = {https://dblp.org/rec/conf/esa/BenderCDF02},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/3-540-45749-6_16">SpringerLink</A>.},
}

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 SpringerLink.

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]