TY - GEN
T1 - Cache-oblivious priority queue and graph algorithm applications
AU - Arge, Lars
AU - Bender, Michael A.
AU - Demaine, Erik D.
AU - Holland-Minkley, Bryan
AU - Munro, J. Ian
PY - 2002
Y1 - 2002
N2 - 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 structure, 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.
AB - 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 structure, 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.
UR - https://www.scopus.com/pages/publications/0036038481
U2 - 10.1145/509948.509950
DO - 10.1145/509948.509950
M3 - Conference contribution
AN - SCOPUS:0036038481
SN - 9781581134957
T3 - Conference Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 268
EP - 276
BT - Proceedings of the 34th Annual ACM Symposium on Theory of Computing
PB - Association for Computing Machinery (ACM)
T2 - 34th Annual ACM Symposium on Theory of Computing, STOC 2002
Y2 - 19 May 2002 through 21 May 2002
ER -