ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-105 | 18th October 2011 23:27

Streaming Graph Computations with a Helpful Advisor

RSS-Feed




Revision #1
Authors: Graham Cormode, Michael Mitzenmacher, Justin Thaler
Accepted on: 18th October 2011 23:27
Downloads: 817
Keywords: 


Abstract:

Motivated 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.



Changes to previous version:

Revised for improved clarity after receiving reviewer comments.


Paper:

TR11-105 | 22nd July 2011 17:42

Streaming Graph Computations with a Helpful Advisor


Abstract:

Motivated 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.



ISSN 1433-8092 | Imprint