Annotations in Data Streams: With a little help from your friends... by Andrew McGregor, UMASS

Abstract: The central goal of data stream computation is to process massive streams of data using sub-linear storage space. We ask whether the space usage of such algorithms can be further reduced by enlisting a more powerful ``helper'' who can annotate the stream as it is read. We do not wish to blindly trust the helper, so we require that the algorithm be convinced of having computed a correct answer. We show upper bounds that achieve a non-trivial tradeoff between the amount of annotation used and the space required to verify it. We also prove lower bounds on such tradeoffs, often nearly matching the upper bounds, via notions related to Merlin-Arthur communication complexity. Our results cover the classic data stream problems of selection, frequency moments, and fundamental graph problems such as triangle- freeness and connectivity. Time permitting we will also discuss some related recent results on verifying data structure transcripts. Includes joint work with Amit Chakrabarti, Graham Cormode, and Ranganath Kondapally.

Joanne Talbot Hanley

Last modified: Mon Aug 16 13:59:16 EDT 2010