Algorithm Design and Engineering Group

Department of Computer and System Sciences, University of Rome "La Sapienza"
welcome people events activities projects software publications

Paper information

In proceedings

Camil Demetrescu, Irene Finocchi, Andrea Ribichini
Trading off space for passes in graph streaming problems
in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06), pp. 714-723, 2006.


A natural question in data stream processing is whether we can reduce the space usage at the price of increasing the number of passes over the data. Unfortunately, this seems to be very hard for many graph problems, unless powerful primitives such as sorting are used. And yet, even using sorting, problems such as shortest paths remain difficult. In this talk we show that, for any space restriction of s bits, single-source shortest paths in directed graphs with small positive integer edge weights can be solved in O((n log^3/2 n)/sqrt(s)) passes. For undirected connectivity, we devise an O((n log n)/s) passes algorithm. Both problems require Omega(n/s) passes under the restrictions we consider. Our algorithms do not use sorting as a primitive and work in the W-Stream model introduced by Aggarwal et al. in FOCS 2004.