Graph Spanners in the Streaming Model: An Experimental Study |
| |
Authors: | Giorgio Ausiello Camil Demetrescu Paolo G Franciosa Giuseppe F Italiano Andrea Ribichini |
| |
Affiliation: | (1) Dipartimento di Informatica e Sistemistica, Sapienza Università di Roma, via Ariosto 25, 00185 Roma, Italy;(2) Dipartimento di Statistica, Probabilità e Statistiche Applicate, Sapienza Università di Roma, piazzale Aldo Moro 5, 00185 Roma, Italy;(3) Dipartimento di Informatica, Sistemi e Produzione, Università di Roma “Tor Vergata”, via del Politecnico 1, 00133 Roma, Italy |
| |
Abstract: | This article reports the results of an extensive experimental analysis of efficient algorithms for computing graph spanners
in the data streaming model, where an (α,β)-spanner of a graph G is a subgraph S⊆G such that for each pair of vertices the distance in S is at most α times the distance in G plus β. To the best of our knowledge, this is the first computational study of graph spanner algorithms in a streaming setting.
We compare experimentally the randomized algorithms proposed by Baswana () and by Elkin (In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007),
Wroclaw, Poland, pp. 716–727, 9–13 July 2007) for general stretch factors with the deterministic algorithm presented by Ausiello et al. (In: Proceedings of the 15th Annual European Symposium on Algorithms (ESA 2007), Engineering and Applications Track, Eilat,
Israel, 8–10 October 2007. LNCS, vol. 4698, pp. 605–617, 2007), designed for building small stretch spanners. All the algorithms we implemented work in a data streaming model where the
input graph is given as a stream of edges in arbitrary order, and all of them need a single pass over the data. Differently
from the algorithm in Ausiello et al., the algorithms in Baswana () and Elkin (In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw,
Poland, pp. 716–727, 9–13 July 2007) need to know in advance the number of vertices in the graph.
The results of our experimental investigation on several input families confirm that all these algorithms are very efficient
in practice, finding spanners with stretch and size much smaller than the theoretical bounds and comparable to those obtainable
by off-line algorithms. Moreover, our experimental findings confirm that small values of the stretch factor are the case of
interest in practice, and that the algorithm by Ausiello et al. tends to produce spanners of better quality than the algorithms by Baswana and Elkin, while still using a comparable amount
of time and space resources.
Work partially supported by the Italian Ministry of University and Research under Project MAINSTREAM “Algorithms for Massive
Information Structures and Data Streams”. A preliminary version of this paper was presented at the 15th Annual European Symposium
on Algorithms (ESA 2007) 5. |
| |
Keywords: | Graph algorithms Graph spanners Data streams Experimental algorithmics Algorithm engineering |
本文献已被 SpringerLink 等数据库收录! |
|