ECCC-Report TR11-105https://eccc.weizmann.ac.il/report/2011/105Comments and Revisions published for TR11-105en-usTue, 18 Oct 2011 23:27:17 +0200
Revision 1
| Streaming Graph Computations with a Helpful Advisor |
Graham Cormode,
Michael Mitzenmacher,
Justin Thaler
https://eccc.weizmann.ac.il/report/2011/105#revision1Motivated by the trend to outsource work to commercial cloud computing services, we consider a variation of the streaming paradigm where a streaming algorithm can be assisted by a powerful helper that can provide annotations to the data stream. We extend previous work on such annotation models by considering a number of graph streaming problems. Without annotations, streaming algorithms for graph problems generally require significant memory; we show that for many standard problems, including all graph problems that can be expressed with totally unimodular integer programming formulations, only constant space (measured in words) is needed for single-pass algorithms given linear-sized annotations. We also obtain protocols achieving essentially optimal tradeoffs between annotation length and memory usage for several important problems, including integer matrix-vector multiplication and a large class of linear programs, as well as shortest $s$-$t$ path in small-diameter graphs. We obtain non-trivial tradeoffs for minimum weight bipartite perfect matching and shortest $s$-$t$ path in general graphs. Tue, 18 Oct 2011 23:27:17 +0200https://eccc.weizmann.ac.il/report/2011/105#revision1
Paper TR11-105
| Streaming Graph Computations with a Helpful Advisor |
Graham Cormode,
Michael Mitzenmacher,
Justin Thaler
https://eccc.weizmann.ac.il/report/2011/105Motivated by the trend to outsource work to commercial cloud computing services, we consider a variation of the streaming paradigm where a streaming algorithm can be assisted by a powerful helper that can provide annotations to the data stream. We extend previous work on such annotation models by considering a number of graph streaming problems. Without annotations, streaming algorithms for graph problems generally require significant memory; we show that for many standard problems, including all graph problems that can be expressed with totally unimodular integer programming formulations, only constant space (measured in words) is needed for single-pass algorithms given linear-sized annotations. We also obtain protocols achieving essentially optimal tradeoffs between annotation length and memory usage for several important problems, including integer matrix-vector multiplication and a large class of linear programs, as well as shortest $s$-$t$ path in small-diameter graphs. We obtain non-trivial tradeoffs for minimum weight bipartite perfect matching and shortest $s$-$t$ path in general graphs. Fri, 05 Aug 2011 05:57:22 +0300https://eccc.weizmann.ac.il/report/2011/105