The Library
Annotations in data streams
Tools
Chakrabarti, Amit, Cormode, Graham, McGregor, Andrew and Thaler, Justin (2014) Annotations in data streams. Transactions on Algorithms, Volume 11 (Number 1). doi:10.1145/2636924 ISSN 1549-6325.
|
PDF
WRAP_Cormode_annotationj.pdf - Accepted Version - Requires a PDF viewer. Download (430Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/2636924
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” 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. Our work is also part of a growing trend - including recent studies of multi-pass 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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Algorithms, Computable functions, Missing observations (Statistics), Computer science -- Mathematics, Data mining | ||||
Journal or Publication Title: | Transactions on Algorithms | ||||
Publisher: | ACM | ||||
ISSN: | 1549-6325 | ||||
Official Date: | August 2014 | ||||
Dates: |
|
||||
Volume: | Volume 11 | ||||
Number: | Number 1 | ||||
DOI: | 10.1145/2636924 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 28 December 2015 | ||||
Date of first compliant Open Access: | 28 December 2015 | ||||
Embodied As: | 1 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year