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.
- Abstract:
-
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.
- 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.