MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Brodal, Gerth Stølting
Katajainen, Jyrki		dblp
dblp
Editor(s):
Arnborg, Stefan
Ivansson, Lars		dblp
dblp
BibTeX cite key*:
Brodal1998b
Title, Booktitle
Title*:
Worst-Case Efficient External-Memory Priority Queues
Booktitle*:
Proceedings of the 6th Scandinavian Workshop on Algorithm Theory (SWAT-98)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Stockholm, Sweden
Language:
English
Event Date*
(no longer used):
July, 8-10
Organization:
Event Start Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Event End Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1432
Number:
Month:
July
Pages:
107-118
Year*:
1998
VG Wort Pages:
ISBN/ISSN:
3-540-64682-5
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
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 < 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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Brodal1998b,
AUTHOR = {Brodal, Gerth Stølting and Katajainen, Jyrki},
 EDITOR = {Arnborg, Stefan and Ivansson, Lars},
 TITLE = {Worst-Case Efficient External-Memory Priority Queues},
 BOOKTITLE = {Proceedings of the 6th Scandinavian Workshop on Algorithm Theory (SWAT-98)},
 PUBLISHER = {Springer},
 YEAR = {1998},
 VOLUME = {1432},
 PAGES = {107--118},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Stockholm, Sweden},
 MONTH = {July},
 ISBN = {3-540-64682-5},
}

Entry last modified by Christine Kiesel, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Gerth Stølting Brodal		Created
01/23/1999 19:55:30
Revisions
10.
9.
8.
7.
6.		Editor(s)
Christine Kiesel
Uwe Brahm
Uwe Brahm
Evelyn Haak
Evelyn Haak		Edit Dates
20.09.2006 17:11:14
04.04.2000 11:23:58
04.04.2000 11:23:47
01/04/99 12:22:07
01.04.99 10:23:12