Streaming Graph Computations with a Helpful Advisor by
Justin Thaler, Harvard
Abstract: The recent explosion in the number and scale of real-world structured
data sets including the web, social networks, and other relational
data has created a pressing need to efficiently process and analyze
massive graphs. This has sparked the study of graph algorithms that
meet the constraints of the standard streaming model: restricted
memory and the ability to make only one pass (or few passes) over
adversarially ordered data. However, many results for graph streams
have been negative; apparently most graph algorithms fundamentally
require flexibility in the way they query edges, and therefore the
combination of adversarial order and limited memory makes many
problems intractable.
Motivated both by a desire to circumvent these negative results, as
well as by the trend to outsource work to commercial cloud computing
services, I will describe a variation of the streaming paradigm in
which a streaming algorithm is allowed access to a powerful advisor
who may annotate the data stream. Extending previous work on such
annotation models, I will show that for many standard problems,
including all graph problems that can be expressed with totally
unimodular integer programming formulations, only $O(1)$ words of
space are needed for single-pass algorithms given linear-sized
annotations. I will also describe a protocol achieving optimal
tradeoffs between annotation length and memory usage for matrix-
vector multiplication, as well as a large class of convex programs,
including all linear programs.
Additionally, I will briefly describe recent work on an extension of
the annotation model in which multiple rounds of interaction are
allowed between the streaming algorithm and the advisor. I will first
explain how Kilian’s Universal Arguments as well as a powerful
construction of Goldwasser, Kalai, and Rothblum can be modified to
work with a streaming verifier, resulting in efficient computationally
and statistically sound protocols for all of NP and log-space uniform
NC respectively. Lastly, I will describe improved and simplified
protocols for a variety of problems of central importance in streaming
and database processing.
Joint work with Graham Cormode, Michael Mitzenmacher, and Ke Yi.
Joanne Talbot Hanley
Last modified: Mon Aug 16 11:12:04 EDT 2010