Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section