Aarhus University Seal

Funnel Heap - A Cache Oblivious Priority Queue

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearch

  • Department of Computer Science
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.
Original languageEnglish
Title of host publicationAlgorithms and Computation : 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21–23, 2002 Proceedings
EditorsProsenijt Bose, Pat Morin
Number of pages10
Publication year2002
ISBN (print)3-540-00142-5
Publication statusPublished - 2002
EventInternational Symposium on Algorithms and Computation - Vancouver, BC, Canada
Duration: 21 Sept 200223 Sept 2002
Conference number: 13


ConferenceInternational Symposium on Algorithms and Computation
ByVancouver, BC
SeriesLecture Notes in Computer Science

    Research areas

  • Binary tree, Data structure, Subroutine, Queue, Priority, Adaptive method

See relations at Aarhus University Citationformats

ID: 280693