Data stream processing has recently received increasing attention as a computational paradigm for dealing with massive data sets. While major progress has been achieved for several fundamental data sketching and statistics problems, there are many problems that seem to be hard in a streaming setting, including most classical graph problems. Relevant examples are graph connectivity and shortest paths, for which linear lower bounds on the "space x passes" product are known. Some recent papers have shown that several graph problems can be solved with one or few passes, if the working memory is large enough to contain all the vertices of the graph. A natural question is whether we can reduce the space usage at the price of increasing the number of passes. Surprisingly, no algorithm with both sublinear space and passes is known for natural graph problems in classical streaming models. Motivated by technological factors of modern storage systems, some authors have recently started to investigate the computational power of less restrictive streaming models. In a FOCS'04 paper, Aggarwal et al. have shown that the use of intermediate temporary streams, combined with the ability to reorder them at each pass for free, yields enough power to solve in polylogarithmic space and passes a variety of problems, including graph connectivity. They leave however as an open question whether problems such as shortest paths can be solved efficiently in this more powerful model. In this paper, we show that the "streaming with sorting" model by Aggarwal et al. can yield interesting results even without using sorting at all: by just using intermediate temporary streams, we provide the first effective spacepasses 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 log(3/2) n)/root 7s) passes. 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 Omega(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.

Trading off space for passes in graph streaming problems / Demetrescu, Camil; FINOCCHI, IRENE; Ribichini, Andrea. - (2006), pp. 714-723. ((Intervento presentato al convegno 17th ACM-SIAM Symposium on Discrete Algorithms tenutosi a Miami, FL nel 22 January 2006 through 24 January 2006 [10.1145/1109557.1109635].

Trading off space for passes in graph streaming problems

Irene Finocchi;
2006

Abstract

Data stream processing has recently received increasing attention as a computational paradigm for dealing with massive data sets. While major progress has been achieved for several fundamental data sketching and statistics problems, there are many problems that seem to be hard in a streaming setting, including most classical graph problems. Relevant examples are graph connectivity and shortest paths, for which linear lower bounds on the "space x passes" product are known. Some recent papers have shown that several graph problems can be solved with one or few passes, if the working memory is large enough to contain all the vertices of the graph. A natural question is whether we can reduce the space usage at the price of increasing the number of passes. Surprisingly, no algorithm with both sublinear space and passes is known for natural graph problems in classical streaming models. Motivated by technological factors of modern storage systems, some authors have recently started to investigate the computational power of less restrictive streaming models. In a FOCS'04 paper, Aggarwal et al. have shown that the use of intermediate temporary streams, combined with the ability to reorder them at each pass for free, yields enough power to solve in polylogarithmic space and passes a variety of problems, including graph connectivity. They leave however as an open question whether problems such as shortest paths can be solved efficiently in this more powerful model. In this paper, we show that the "streaming with sorting" model by Aggarwal et al. can yield interesting results even without using sorting at all: by just using intermediate temporary streams, we provide the first effective spacepasses 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 log(3/2) n)/root 7s) passes. 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 Omega(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.
9780898716054
data streaming; shortest path algorithms; connected components
Trading off space for passes in graph streaming problems / Demetrescu, Camil; FINOCCHI, IRENE; Ribichini, Andrea. - (2006), pp. 714-723. ((Intervento presentato al convegno 17th ACM-SIAM Symposium on Discrete Algorithms tenutosi a Miami, FL nel 22 January 2006 through 24 January 2006 [10.1145/1109557.1109635].
File in questo prodotto:
File Dimensione Formato  
p714-demetrescu.pdf

Solo gestori archivio

Tipologia: Documento in Post-print
Licenza: DRM non definito
Dimensione 214.02 kB
Formato Adobe PDF
214.02 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/192681
Citazioni
  • Scopus 46
  • ???jsp.display-item.citation.isi??? 26
social impact