 | The ACM Journal of Experimental Algorithmics |
Volume 5, Article 17, 2000
An Experimental Study of Priority Queues in External Memory
by
Klaus Brengel
and
and
and
http://www.jea.acm.org/2000/BrengelPriority/
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, whereas the others are standard
internal-memory queues available in the LEDA library.
Two of the external-memory priority queues are obtained by
engineering known internal-memory priority queues with the aim of
achieving effective performances on external storage devices (i.e.,
Radix heaps and array heaps). Our
experimental framework includes some simple tests, like random
sequences of insert or delete-minimum operations, as well 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 variegated 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.
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The software suite accompanying the
article; this is a small Unix tar file, which includes the source code,
a Makefile, and the test files used in the article.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
|
|
|
|
Last updated and validated October 11, 2001, by editor@jea.acm.org