{"controller"=>"catalog", "action"=>"show", "id"=>"242414355"}
  • EN
  • DA

Danish NationalResearch Database

  • Search Publications & Researchers
  • Open Access Indicator
  • Publications
  • Researchers
Example Finds records
water{} containing the word "water".
water supplies"{}" containing the phrase "water supplies".
author:"Doe, John"author:"{}" containing the prase "Doe, John" in the author field.
title:IEEEtitle:{} containing the word "IEEE" in the title field.
Need more help? Advanced search tutorial
  • Selected (0)
  • History

Funnel Heap - A Cache Oblivious Priority Queue

    • Save to Mendeley
    • Export to BibTeX
    • Export to RIS
    • Email citation
Authors:
  • Brodal, Gerth Stølting ;
    Close
    Orcid logo0000-0001-9054-915X
    Department of Computer Science, Science and Technology, Aarhus University
  • Fagerberg, Rolf
    Close
    unknown
Editor:
Bose, Prosenjit3, Morin, Pat, Bose, Prosenijt
DOI:
10.1007/3-540-36136-7_20
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.
ISBN:
3540001425
Type:
Conference paper
Language:
English
Published in:
Lecture Notes in Computer Science: 13th International Symposium, Isaac 2002 Vancouver, Bc, Canada, November 21–23, 2002 Proceedings, 2002, p. 219-228
Keywords:
Binary tree; Data structure; Subroutine; Queue; Priority; Adaptive method
Main Research Area:
Science/technology
Publication Status:
Published
Series:
Lecture Notes in Computer Science
Review type:
Undetermined
Conference:
International Symposium on Algorithms and Computation, 2002
Publisher:
Springer
Submission year:
2002
Scientific Level:
Scientific
ID:
242414355

Full text access

  • Doi Get publisher edition via DOI resolver
Checking for on-site access...

On-site access

At institution

  • Aarhus university.en
Feedback

Sitemap

  • Search
    • Statistics
    • Tutorial
    • Data
    • FAQ
    • Contact
  • Open Access
    • Overview
    • Development
    • FAQ
    • Contact
  • About
    • Institutions
    • Release History
    • Cookies and privacy policy

Copyright © 1998–2018.

Fivu en