- Authors:
- 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
Checking for on-site access...
