hide
Free keywords:
-
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.
