Data stream processing has recently received increasing attention as a computational paradigm for dealing with massive data sets. Surprisingly, no algorithm with both sublinear space and passes is known for natural graph problems in classical read-only streaming. Motivated by technological factors of modern storage systems, some authors have recently started to investigate the computational power of less restrictive models where writing streams is allowed. In this article, we show that the use of intermediate temporary streams is powerful enough to provide effective space-passes tradeoffs for natural graph problems. In particular, for any space restriction of s bits, we show that single-source shortest paths in directed graphs with small positive integer edge weights can be solved in O((n log3/2 n)/√s) passes. The result can be generalized to deal with multiple sources within the same bounds. This is the first known streaming algorithm for shortest paths in directed graphs. For undirected connectivity, we devise an O((n log n)/s) passes algorithm. Both problems require ω(n/s) passes under the restrictions we consider. We also show that the model where intermediate temporary streams are allowed can be strictly more powerful than classical streaming for some problems, while maintaining all of its hardness for others. © 2009 ACM.

Trading off space for passes in graph streaming problems / Demetrescu, Camil; Finocchi, Irene; Ribichini, Andrea. - In: ACM TRANSACTIONS ON ALGORITHMS. - ISSN 1549-6325. - 6:1(2009), pp. 1-17. [10.1145/1644015.1644021]

Trading off space for passes in graph streaming problems

FINOCCHI, Irene;
2009

Abstract

Data stream processing has recently received increasing attention as a computational paradigm for dealing with massive data sets. Surprisingly, no algorithm with both sublinear space and passes is known for natural graph problems in classical read-only streaming. Motivated by technological factors of modern storage systems, some authors have recently started to investigate the computational power of less restrictive models where writing streams is allowed. In this article, we show that the use of intermediate temporary streams is powerful enough to provide effective space-passes tradeoffs for natural graph problems. In particular, for any space restriction of s bits, we show that single-source shortest paths in directed graphs with small positive integer edge weights can be solved in O((n log3/2 n)/√s) passes. The result can be generalized to deal with multiple sources within the same bounds. This is the first known streaming algorithm for shortest paths in directed graphs. For undirected connectivity, we devise an O((n log n)/s) passes algorithm. Both problems require ω(n/s) passes under the restrictions we consider. We also show that the model where intermediate temporary streams are allowed can be strictly more powerful than classical streaming for some problems, while maintaining all of its hardness for others. © 2009 ACM.
shortest paths; data streaming; graph connectivity
Trading off space for passes in graph streaming problems / Demetrescu, Camil; Finocchi, Irene; Ribichini, Andrea. - In: ACM TRANSACTIONS ON ALGORITHMS. - ISSN 1549-6325. - 6:1(2009), pp. 1-17. [10.1145/1644015.1644021]
File in questo prodotto:
File Dimensione Formato  
ACMTALG2009.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM non definito
Dimensione 292.67 kB
Formato Adobe PDF
292.67 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/192595
Citazioni
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 13
social impact