Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2020) |
last year
(2019) |
two years ago
(2018) |
Notes URL
Action:
login to update
Options:
Goto entry point
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
URL of the conference:
URL for downloading the paper:
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
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 07:55:30 PM
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
Attachment Section
Attachment Section