Paper by Erik D. Demaine

Reference:

Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan E. Holland-Minkley, and J. Ian Munro, “An Optimal Cache-Oblivious Priority Queue and its Application to Graph Algorithms”, SIAM Journal on Computing, volume 36, number 6, March 2007, pages 1672–1695.

BibTeX

@Article{BufferTrees_SICOMP,
  AUTHOR        = {Lars Arge and Michael A. Bender and Erik D. Demaine and
                   Bryan E. Holland-Minkley and J. Ian Munro},
  TITLE         = {An Optimal Cache-Oblivious Priority Queue and its
                   Application to Graph Algorithms},
  JOURNAL       = {SIAM Journal on Computing},
  journalurl    = {http://www.siam.org/journals/sicomp/sicomp.htm},
  VOLUME        = 36,
  NUMBER        = 6,
  PAGES         = {1672--1695},
  MONTH         = {March},
  YEAR          = 2007,

  length        = {26 pages},
  papers        = {BufferTrees_STOC2002},
  replaces      = {BufferTrees_STOC2002},
  doi           = {https://dx.doi.org/10.1137/S0097539703428324},
  dblp          = {https://dblp.org/rec/journals/siamcomp/ArgeBDHM07},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1137/S0097539703428324">SIAM</A>.},
}

Abstract:

We develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and delete-min 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. Our structure is as efficient as 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 SIAM.

Length:

The paper is 26 pages.

Availability:

The paper is available in PostScript (471k) and gzipped PostScript (193k).

See information on file formats.

[Google Scholar search]

Related papers:

BufferTrees_STOC2002 (Cache-Oblivious Priority Queue and Graph Algorithm Applications)