ID:
517959.0,
MPI für Informatik / Algorithms and Complexity Group 
WorstCase Efficient ExternalMemory Priority Queues 
Authors:  Brodal, Gerth Stølting; Katajainen, Jyrki 
Language:  English 
Publisher:  Springer 
Place of Publication:  Berlin, Germany 
Date of Publication (YYYYMMDD):  1998 
Title of Proceedings:  Proceedings of the 6th Scandinavian Workshop on Algorithm Theory (SWAT98) 
Start Page:  107 
End Page:  118 
Title of Series:  Lecture Notes in Computer Science 
Place of Conference/Meeting:  Stockholm, Sweden 
Audience:  Experts Only 
Intended Educational Use:  No 
Abstract / Description:  A priority queue $Q$ is a data structure that maintains a collection of elements, each element having an associated priority drawn from a totally ordered universe, under the operations {\sc Insert}, which inserts an element into $Q$, and {\sc DeleteMin}, which deletes an element with the minimum priority from $Q$. In this paper a priorityqueue implementation is given which is efficient with respect to the number of block transfers or I/Os performed between the internal and external memories of a computer. Let $B$ and $M$ denote the respective capacity of a block and the internal memory measured in elements. The developed data structure handles any intermixed sequence of {\sc Insert} and {\sc DeleteMin} operations such that in every disjoint interval of $B$ consecutive priorityqueue operations at most $c \log_{M/B} \frac{N}{M}$ I/Os are performed, for some positive constant $c$. These I/Os are divided evenly among the operations: if $B \geq c \log_{M/B} \frac{N}{M}$, one I/O is necessary for every $B/(c\log_{M/B} \frac{N}{M})$th operation and if $B < c \log_{M/B} \frac{N}{M}$, $\frac{c}{B}\log_{M/B} \frac{N}{M}$ I/Os are performed per every operation. Moreover, every operation requires $O(\log_2 N)$ comparisons in the worst case. The best earlier solutions can only handle a sequence of $S$ operations with $O(\sum_{i=1}^{S}\frac{1}{B}\log_{M/B}\frac{N_{i}}{M})$ I/Os, where $N_{i}$ denotes the number of elements stored in the data structure prior to the $i$th operation, without giving any guarantee for the performance of the individual operations. 
Last Change of the Resource (YYYYMMDD):  20100302 
External Publication Status:  published 
Document Type:  ConferencePaper 
Communicated by:  Kurt Mehlhorn 
Affiliations:  MPI für Informatik/Algorithms and Complexity Group

Identifiers:  LOCALID:C1256428004B93B8AE17AD70BAC468B9C12567020067F566... ISBN:3540646825 
