------------------------------
I'm happy to write a guest post announcing a new paper, "Streaming Graph Computations with a Helpful Advisor (arxiv link)" by me, Michael, and Graham Cormode of AT&T Labs -- Research. In our paper, we consider a variation of the streaming paradigm in which a streaming algorithm is allowed access to a powerful advisor who may annotate the data stream. We're primarily motivated by the emergence of commercial cloud computing services, like Amazon EC2, but we also have in mind other settings in which outsourcing of computation is desirable, such as weak peripheral devices that need to delegate computation they cannot handle on their own.
In many of our motivating applications, the helper is not a trusted entity; the commercial stream processing service may have executed a buggy algorithm, experienced a hardware fault or communication error, or may even be deliberately deceptive. For example, since executing a computation is costly, a cloud computing service may have a financial incentive not to complete the computation they were hired to perform, as long as they can convince their client otherwise. As a result, we would like the helper to prove that she executed the computation correctly, especially if providing the proof is not too costly.
In our paper, we primarily consider problems on graph streams, which are of high interest given the recent explosion in the number and scale of real-world structured data sets including the web, social networks, and other relational data. 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 in the standard streaming model. Consequently, these problems are ripe for outsourcing.
We prove a host of positive results for many standard graph problems in our model, many of which are optimal or near-optimal. We also provide a protocol achieving optimal tradeoffs between proof-length and working memory for matrix-vector multiplication, which is my personal favorite.
While we're introducing our paper to the blogosphere, it seems worthwhile to mention some other blog posts closely related to our work. Richard Lipton describes work by himself, Atish Das Sarma and Danupon Nanongkai on the Best Order Streaming Model which happens to be a special case of our own
http://rjlipton.wordpress.com/
In a more recent post, Professor Lipton describes a different notion of "security" in Cloud Computing.
http://rjlipton.wordpress.com/
The concern there is on keeping the data private, and without explicit streaming constraints, but it's good to see other emphasis on trust within outsourced computations.
3 comments:
We prove a host of positive results for
many standard graph problems in our model, many of which are optimal or near-optimal.
You do a fine job of describing motivation. But, to.
To better advertise your paper, it would be helpful to specifically state (at least) one of the results.
Having 'a helpful advisor' is critical to a grad student. [giggle].
michael, that you had to put this -- "(I note, in line with current discussions, the author list is in alphabetical order, but as Justin is the student, you can rightfully assume he did most of the work.)"--
doesnt speak too well of ur alphabetical ordering policy does it?
i mean, if u didnt want to clear it in the paper, then why say it now? double work? :)
Post a Comment