{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:43:12Z","timestamp":1774946592641,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,8,25]],"date-time":"2014-08-25T00:00:00Z","timestamp":1408924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000005","name":"U.S. Department of Defense","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000005","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,10,28]]},"abstract":"<jats:p>\n            The central goal of data stream algorithms is to process massive streams of data using\n            <jats:italic>sublinear<\/jats:italic>\n            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 \u201chelper\u201d that can\n            <jats:italic>annotate<\/jats:italic>\n            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\u2014including recent studies of multipass streaming, read\/write streams, and randomly ordered streams\u2014of 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.\n          <\/jats:p>","DOI":"10.1145\/2636924","type":"journal-article","created":{"date-parts":[[2014,8,29]],"date-time":"2014-08-29T13:03:31Z","timestamp":1409317411000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Annotations in Data Streams"],"prefix":"10.1145","volume":"11","author":[{"given":"Amit","family":"Chakrabarti","sequence":"first","affiliation":[{"name":"Dartmouth College, Hanover, NH"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Graham","family":"Cormode","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Mcgregor","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Justin","family":"Thaler","sequence":"additional","affiliation":[{"name":"Simons Institute for the Theory of Computing, UC Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,8,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.36"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374481"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00157-3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.48"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.82"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.15"},{"key":"e_1_2_1_8_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms. 623--632","author":"Bar-Yossef Ziv","unstructured":"Ziv Bar-Yossef , Ravi Kumar , and D. Sivakumar . 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs . In ACM-SIAM Symposium on Discrete Algorithms. 623--632 . Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs. In ACM-SIAM Symposium on Discrete Algorithms. 623--632."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.52"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250891"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806729"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Vladimir Braverman and Rafail Ostrovsky. 2013. Generalizing the Layering method of Indyk and Woodruff: recursive sketches for frequency-based vectors on streams. In APPROX-RANDOM. 58--70.  Vladimir Braverman and Rafail Ostrovsky. 2013. Generalizing the Layering method of Indyk and Woodruff: recursive sketches for frequency-based vectors on streams. In APPROX-RANDOM. 58--70.","DOI":"10.1007\/978-3-642-40328-6_5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374470"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_20"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214414"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1781574.1781632"},{"key":"e_1_2_1_19_1","volume-title":"International Conference on Very Large Data Bases. 464--475","author":"Cormode G.","unstructured":"G. Cormode , F. Korn , S. Muthukrishnan , and D. Srivastava . 2003. Finding hierarchical heavy hitters in data streams . In International Conference on Very Large Data Bases. 464--475 . G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava. 2003. Finding hierarchical heavy hitters in data streams. In International Conference on Very Large Data Bases. 464--475."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090245"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9598-y"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2047485.2047488"},{"key":"e_1_2_1_24_1","volume-title":"European Symposium on Algorithms","volume":"2461","author":"Datar M.","unstructured":"M. Datar and S. Muthukrishnan . 2002. Estimating rarity and similarity over data stream Windows . In European Symposium on Algorithms , Vol. 2461 . 323--334. M. Datar and S. Muthukrishnan. 2002. Estimating rarity and similarity over data stream Windows. In European Symposium on Algorithms, Vol. 2461. 323--334."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109635"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.030"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09526-8_5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a010"},{"key":"e_1_2_1_32_1","volume-title":"NP and streaming verifiers. Manuscript","author":"Gertner Yael","year":"2002","unstructured":"Yael Gertner , Sampath Kannan , and Mahesh Viswanathan . 2002. NP and streaming verifiers. Manuscript ( 2002 ). Yael Gertner, Sampath Kannan, and Mahesh Viswanathan. 2002. NP and streaming verifiers. Manuscript (2002)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374396"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142387"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_45"},{"key":"e_1_2_1_36_1","volume-title":"Computing on data streams. External Memory Algorithms","author":"Henzinger Monika R.","year":"1999","unstructured":"Monika R. Henzinger , Prabhakar Raghavan , and Sridhar Rajagopalan . 1999. Computing on data streams. External Memory Algorithms ( 1999 ), 107--118. Monika R. Henzinger, Prabhakar Raghavan, and Sridhar Rajagopalan. 1999. Computing on data streams. External Memory Algorithms (1999), 107--118."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/2958119.2958158"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90224-W"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214415"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.33"},{"key":"e_1_2_1_42_1","volume-title":"Communication Complexity","author":"Kushilevitz Eyal","unstructured":"Eyal Kushilevitz and Noam Nisan . 1997. Communication Complexity . Cambridge University Press . Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press."},{"key":"e_1_2_1_43_1","unstructured":"Feifei Li Ke Yi Marios Hadjieleftheriou and George Kollios. 2007. Proof-infused streams: Enabling authentication of sliding window queries on streams. In VLDB. 147--158.   Feifei Li Ke Yi Marios Hadjieleftheriou and George Kollios. 2007. Proof-infused streams: Enabling authentication of sliding window queries on streams. In VLDB. 147--158."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_1_45_1","volume-title":"Data Streams: Algorithms and Applications","author":"Muthukrishnan S.","year":"2006","unstructured":"S. Muthukrishnan . 2006 . Data Streams: Algorithms and Applications . Now Publishers . S. Muthukrishnan. 2006. Data Streams: Algorithms and Applications. Now Publishers."},{"key":"e_1_2_1_46_1","volume-title":"CADS: Continuous authentication on data streams. In VLDB. 135--146.","author":"Papadopoulos Stavros","year":"2007","unstructured":"Stavros Papadopoulos , Yin Yang , and Dimitris Papadias . 2007 . CADS: Continuous authentication on data streams. In VLDB. 135--146. Stavros Papadopoulos, Yin Yang, and Dimitris Papadias. 2007. CADS: Continuous authentication on data streams. In VLDB. 135--146."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009378.1009562"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Alexander Razborov. 1990. On the distributional complexity of disjontness. In International Colloquium on Automata Languages and Programming. 249--253.   Alexander Razborov. 1990. On the distributional complexity of disjontness. In International Colloquium on Automata Languages and Programming. 249--253.","DOI":"10.1007\/BFb0032036"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214026"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488725"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, J. Ian Munro (Ed.). SIAM, 615--624","author":"Thorup Mikkel","year":"2004","unstructured":"Mikkel Thorup and Yin Zhang . 2004 . Tabulation based 4-universal hashing with applications to second moment estimation . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, J. Ian Munro (Ed.). SIAM, 615--624 . Mikkel Thorup and Yin Zhang. 2004. Tabulation based 4-universal hashing with applications to second moment estimation. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, J. Ian Munro (Ed.). SIAM, 615--624."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198390"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497450"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201908)","author":"Zelke Mariano","year":"2008","unstructured":"Mariano Zelke . 2008 . Weighted matching in the semi-streaming model . In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201908) . 669--680. Mariano Zelke. 2008. Weighted matching in the semi-streaming model. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201908). 669--680."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2636924","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2636924","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:22Z","timestamp":1750231162000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2636924"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,25]]},"references-count":54,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,10,28]]}},"alternative-id":["10.1145\/2636924"],"URL":"https:\/\/doi.org\/10.1145\/2636924","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,25]]},"assertion":[{"value":"2012-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}