Please note that eDoc will be permanently shut down in the first quarter of 2021! Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

 Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents

ID: 517959.0, MPI für Informatik / Algorithms and Complexity Group
Worst-Case Efficient External-Memory Priority Queues
Authors:
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):1998
Title of Proceedings:Proceedings of the 6th Scandinavian Workshop on Algorithm Theory (SWAT-98)
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
priority-queue 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 priority-queue
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 &lt; 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 (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations: