Funnel Heap - A Cache Oblivious Priority Queue

Gerth Stølting Brodal and Rolf Fagerberg

In Proc. 13th Annual International Symposium on Algorithms and Computation, volume 2518 of Lecture Notes in Computer Science, pages 219-228. Springer Verlag, Berlin, 2002.

Abstract

The cache oblivious model of computation is a two-level memory model with the assumption that the parameters of the model are unknown to the algorithms. A consequence of this assumption is that an algorithm efficient in the cache oblivious model is automatically efficient in a multi-level memory model. Arge et al. recently presented the first optimal cache oblivious priority queue, and demonstrated the importance of this result by providing the first cache oblivious algorithms for graph problems. Their structure uses cache oblivious sorting and selection as subroutines. In this paper, we devise an alternative optimal cache oblivious priority queue based only on binary merging. We also show that our structure can be made adaptive to different usage profiles.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2002. All rights reserved.

Online version

isaac02.pdf (143 Kb)

DOI

10.1007/3-540-36136-7_20

Links

Slides

isaac02.pdf (157 Kb)

BIBTEX entry

@incollection{isaac02,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg",
  booktitle = "Proc. 13th Annual International Symposium on Algorithms and Computation",
  doi = "10.1007/3-540-36136-7_20",
  isbn = "978-3-540-00142-3",
  pages = "219-228",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Funnel Heap - A Cache Oblivious Priority Queue",
  volume = "2518",
  year = "2002"
}

Other versions