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