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 BibTeX file.
Last updated June 13, 2024 by Erik Demaine.