Annotations in Data Streams
Abstract
The central goal of data stream algorithms is to process massive streams of data using sublinear storage space. Motivated by work in the database community on outsourcing database and data stream processing, we ask whether the space usage of such algorithms can be further reduced by enlisting a more powerful “helper” that 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 nontrivial 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. Our work is also part of a growing trend—including recent studies of multipass streaming, read/write streams, and randomly ordered streams—of asking more complexity-theoretic questions about data stream processing. It is a recognition that, in addition to practical relevance, the data stream model raises many interesting theoretical questions in its own right.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 25, 2014
- Source ID
- 10.1145/2636924
Entities
People
- Amit Chakrabarti
- Andrew Mcgregor
- Graham Cormode
- Justin Thaler
Organizations
- Dartmouth College
- Division of Computing and Communication Foundations
- Division of Information and Intelligent Systems
- National Science Foundation
- United States Department of Defense
- University of California, Berkeley
- University of Massachusetts Amherst
- University of Warwick