@conference{MO09,
author = "Ulrich Meyer and Vitaly Osipov",
abstract = "We report on initial experimental results for a
practical I/O-efficient Single-Source Shortest-Paths (SSSP)
algorithm on general undirected sparse graphs where
the ratio between the largest and the smallest edge weight
is reasonably bounded (for example integer weights in $\{1, \ldots,
2^{32}\}$) and the realistic assumption holds that
main memory is big enough to keep one bit per vertex.
While our implementation only guarantees average-case
efficiency, i.e., assuming randomly chosen edge-weights, it turns out
that its performance on real-world instances with non-random edge
weights is actually even better than on the respective inputs with
random weights.
Furthermore, compared to the currently best implementation for external-memory BFS,
which in a sense constitutes a lower bound for SSSP,
the running time of our approach always stayed within a factor of five, for the most difficult
graph classes the difference was even less than a factor of two.
We are not aware of any previous I/O-efficient implementation for the classic
general SSSP in a (semi)
external setting:
in two recent projects Kumar/Schwabe-like SSSP approaches
on graphs of at most 6 million vertices have been tested,
forcing the authors to artificially restrict the main memory size, $M$, to rather unrealistic 4 to 16 MBytes
in order not to leave the semi-external setting or produce huge running times for larger graphs:
for random graphs of $2^{20}$ vertices, the best previous approach needed over six hours.
In contrast, for a similar ratio of input size vs. $M$, but on a 128 times larger and even sparser
random graph, our approach was less than seven times slower, a relative gain of nearly 20.
On a real-world 24 million node street graph, our implementation was over 40 times faster.
Even larger gains of over 500 can be estimated for random line graphs
based on previous experimental results for Munagala/Ranade-BFS.
Finally, we also report on early results of experiments in which we replace the hard disk by a
solid state disk (flash memory). ",
address = " ",
booktitle = "10th Workshop on Algorithm Engineering and Experiments (ALENEX)",
crossref = " ",
editor = " ",
month = " ",
number = " ",
organization = " ",
pages = "85--96",
publisher = " ",
series = " ",
title = "{D}esign and {I}mplementation of a {P}ractical {I}/{O}-efficient {S}hortest {P}aths {A}lgorithm",
url = "http://www.siam.org/proceedings/alenex/2009/alx09_009_meyeru.pdf ",
volume = " ",
year = "2009",
}