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: 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:

 (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},