Streaming Graph Computations with a Helpful Advisor

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, as well as shortest s‐t path in small‐diameter graphs. We also obtain non‐trivial tradeoffs for minimum weight bipartite perfect matching and shortest s‐t path in general graphs.