Paper by Erik D. Demaine
- 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.
In this paper we develop an optimal cache-oblivious priority queue data
structure, supporting insertion, deletion, and deletemin operations in
O((1/B) logM/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.
- The paper is 9 pages.
- 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated February 24, 2021 by