Unpublished, Draft, To Appear
@UnPublished
Unveröffentlicht, Entwurf


Show entries of:

this year (2022) | last year (2021) | two years ago (2020) | Notes URL

Action:

login to update
Options:









Author, Editor
Author(s):
Crauser, Andreas
Meyer, Ulrich
Brengel, Klaus		dblp
dblp
dblp

BibTeX citekey*:

Crauser2000

Title, Booktitle

Title*:

An experimental study of priority queues in external memory

Vol, No, pp., Year

Month:


Year:

2001

Language:

English
Pages:

24

Abstract, Links, ©

Note:


LaTeX Abstract:

In this paper we compare the performance of eight different priority
queue implementations: four of them are explicitly designed to work
in an external-memory setting, the others are standard
internal-memory queues available in the LEDA library~\cite{leda}.
Two of the external-memory priority queues are obtained by
engineering known internal-memory priority queues with the aim of
achieving effective performance on external storage devices (i.e.,
Radix heaps~\cite{Ahuja-et-al} and array heaps~\cite{Thorup}). Our
experimental framework includes some simple tests, like random
sequences of insert or delete-minimum operations, as well as more
advanced tests consisting of intermixed sequences of update
operations and ``application driven'' update sequences originated
by simulations of Dijkstra's algorithm on large graph instances.
Our variegate spectrum of experimental results gives a good picture
of the features of these priority queues, thus being helpful to
anyone interested in the use of such data structures on very large
data sets.

Categories / Keywords:

external memory, priority queues

HyperLinks / References / URLs:


Personal Comments:


File Upload:




Download
Access Level:


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

BibTeX Entry:
@UNPUBLISHED{Crauser2000,
AUTHOR = {Crauser, Andreas and Meyer, Ulrich and Brengel, Klaus},
 TITLE = {An experimental study of priority queues in external memory},
 JOURNAL = {Journal of Experimental Algorithmics},
 PUBLISHER = {ACM},
 YEAR = {2001},
 NUMBER = {??},
 VOLUME = {5},
 PAGES = {24},
 ADDRESS = {New York, USA},
 ISBN = {1084-6654},
}

Entry last modified by Uwe Brahm, 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)
Andreas Crauser		Created
02/23/2001 05:03:05 PM
Revisions
5.
4.
3.
2.
1.		Editor(s)
Uwe Brahm
Ulrich Meyer
Ulrich Meyer
Anja Becker
Anja Becker		Edit Dates
01/18/2002 07:10:54 PM
08/01/2002 12:33:36
08/01/2002 11:47:55
04.04.2001 15:38:36
20.03.2001 17:07:08