Paper by Erik D. Demaine

Reference:

Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, and J. Ian Munro, “Cache-Oblivious Priority Queue and Graph Algorithm Applications”, in Proceedings of the 34th ACM Symposium on Theory of Computing (STOC 2002), Montréal, Québec, Canada, May 19–21, 2002, pages 268–276.

BibTeX

@InProceedings{BufferTrees_STOC2002,
  AUTHOR        = {Lars Arge and Michael A. Bender and Erik D. Demaine and
                   Bryan Holland-Minkley and J. Ian Munro},
  TITLE         = {Cache-Oblivious Priority Queue and Graph Algorithm
                   Applications},
  BOOKTITLE     = {Proceedings of the 34th ACM Symposium on Theory of
                   Computing (STOC 2002)},
  BOOKURL       = {http://www.crm.umontreal.ca/STOC02/},
  ADDRESS       = {Montr\'eal, Qu\'ebec, Canada},
  MONTH         = {May 19--21},
  YEAR          = 2002,
  PAGES         = {268--276},

  length        = {9 pages},
  papers        = {BufferTrees_SICOMP},
  doi           = {https://dx.doi.org/10.1145/509907.509950},
  dblp          = {https://dblp.org/rec/conf/stoc/ArgeBDHM02},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1145/509907.509950">ACM</A>.},
}

Abstract:

In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O((1/B) log_M/B (N/B)) amortized memory transfers, where M and B are the memory and block transfer sizes of any two consecutive levels of a multilevel memory hierarchy. In a cache-oblivious data structure, M and B are not used in the description of the structure. The bounds match the bounds of several previously developed external-memory (cache-aware) priority queue data structures, which all rely crucially on knowledge about M and B. Priority queues are a critical component in many of the best known external-memory graph algorithms, and using our cache-oblivious priority queue we develop several cache-oblivious graph algorithms.

Comments:

This paper is also available from ACM.

Length:

The paper is 9 pages.

Availability:

The paper is available in PostScript (245k), gzipped PostScript (93k), and PDF (186k).

See information on file formats.

[Google Scholar search]

Related papers:

BufferTrees_SICOMP (An Optimal Cache-Oblivious Priority Queue and its Application to Graph Algorithms)