{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:38Z","timestamp":1760202578721,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029264"},{"type":"electronic","value":"9783642029271"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02927-1_20","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T08:37:10Z","timestamp":1246696630000},"page":"222-234","source":"Crossref","is-referenced-by-count":20,"title":["Annotations in Data Streams"],"prefix":"10.1007","author":[{"given":"Amit","family":"Chakrabarti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Graham","family":"Cormode","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"McGregor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Wigderson, A.: Algebrization: a new barrier in complexity theory. In: ACM STOC (2008)","DOI":"10.1145\/1374376.1374481"},{"issue":"2","key":"20_CR2","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0304-3975(95)00157-3","volume":"175","author":"F. Ablayev","year":"1996","unstructured":"Ablayev, F.: Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theoretical Computer Science\u00a0175(2), 139\u2013159 (1996)","journal-title":"Theoretical Computer Science"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Datar, M., Rajagopalan, S., Ruhl, M.: On the streaming model augmented with a sorting primitive. In: IEEE FOCS (2004)","DOI":"10.1109\/FOCS.2004.48"},{"issue":"1","key":"20_CR4","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. Journal of Computer and System Sciences\u00a058(1), 137\u2013147 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Babai, L., Frankl, P., Simon, J.: Complexity classes in communication complexity theory (preliminary version). In: IEEE FOCS (1986)","DOI":"10.1109\/SFCS.1986.15"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: ACM-SIAM SODA (2002)","DOI":"10.1145\/380752.380810"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Beame, P., Huynh-Ngoc, D.-T.: On the value of multiple read\/write streams for approximating frequency moments. In: IEEE FOCS (2008)","DOI":"10.1109\/FOCS.2008.52"},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Beame, P., Jayram, T.S., Rudra, A.: Lower bounds for randomized read\/write stream algorithms. In: ACM STOC (2007)","DOI":"10.1145\/1250790.1250891"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Buriol, L.S., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., Sohler, C.: Counting triangles in data streams. In: ACM PODS (2006)","DOI":"10.1145\/1142351.1142388"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Cormode, G., McGregor, A.: Robust lower bounds for communication and stream computation. In: ACM STOC (2008)","DOI":"10.1145\/1374376.1374470"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Khot, S., Sun, X.: Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In: IEEE CCC (2003)","DOI":"10.1109\/CCC.2003.1214414"},{"issue":"1","key":"20_CR12","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(03)00400-6","volume":"312","author":"M. Charikar","year":"2004","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. Theor. Comput. Sci.\u00a0312(1), 3\u201315 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"20_CR13","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G. Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. J. Algorithms\u00a055(1), 58\u201375 (2005)","journal-title":"J. Algorithms"},{"key":"20_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-540-74456-6_19","volume-title":"Mathematical Foundations of Computer Science 2007","author":"C. Demetrescu","year":"2007","unstructured":"Demetrescu, C., Escoffier, B., Moruz, G., Ribichini, A.: Adapting parallel algorithms to the W-stream model, with applications to graph problems. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 194\u2013205. Springer, Heidelberg (2007)"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Finocchi, I., Ribichini, A.: Trading off space for passes in graph streaming problems. In: ACM-SIAM SODA (2006)","DOI":"10.1145\/1109557.1109635"},{"issue":"2-3","key":"20_CR16","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J. Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theoretical Computer Science\u00a0348(2-3), 207\u2013216 (2005)","journal-title":"Theoretical Computer Science"},{"key":"20_CR17","unstructured":"Feigenbaum, J., Kannan, S., Zhang, J.: Annotation and computational geometry in the streaming model. Technical Report YALEU\/DCS\/TR-1249, Yale University (2003)"},{"key":"20_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09526-8_5","volume-title":"Mathematical Foundations of Computer Science 1979","author":"R. Freivalds","year":"1979","unstructured":"Freivalds, R.: Fast probabilistic algorithms. In: Becvar, J. (ed.) MFCS 1979. LNCS, vol.\u00a074, Springer, Heidelberg (1979)"},{"key":"20_CR19","unstructured":"Gertner, Y., Kannan, S., Viswanathan, M.: NP and streaming verifiers (manuscript, 2002)"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Grohe, M., Hernich, A., Schweikardt, N.: Randomized computations on large data sets: tight lower bounds. In: ACM PODS (2006)","DOI":"10.1145\/1142351.1142387"},{"key":"20_CR21","doi-asserted-by":"crossref","unstructured":"Henzinger, M.R., Raghavan, P., Rajagopalan, S.: Computing on data streams. In: External memory algorithms (1999)","DOI":"10.1090\/dimacs\/050\/05"},{"key":"20_CR22","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W. Johnson","year":"1984","unstructured":"Johnson, W., Lindenstrauss, J.: Extensions of Lipshitz mapping into Hilbert space. Contemporary Mathematics\u00a026, 189\u2013206 (1984)","journal-title":"Contemporary Mathematics"},{"key":"20_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1007\/11533719_72","volume-title":"Computing and Combinatorics","author":"H. Jowhari","year":"2005","unstructured":"Jowhari, H., Ghodsi, M.: New streaming algorithms for counting triangles in graphs. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 710\u2013716. Springer, Heidelberg (2005)"},{"issue":"2","key":"20_CR24","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0020-0190(93)90224-W","volume":"45","author":"T. Kimbrel","year":"1993","unstructured":"Kimbrel, T., Sinha, R.K.: A probabilistic algorithm for verifying matrix products using o(n 2) time and log2 n\u2009+\u2009o(1) random bits. Inf. Process. Lett.\u00a045(2), 107\u2013110 (1993)","journal-title":"Inf. Process. Lett."},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"Klauck, H.: Rectangle size bounds and threshold covers in communication complexity. In: IEEE CCC (2003)","DOI":"10.1109\/CCC.2003.1214415"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. CUP (1997)","DOI":"10.1017\/CBO9780511574948"},{"key":"20_CR27","unstructured":"Li, F., Yi, K., Hadjieleftheriou, M., Kollios, G.: Proof-infused streams: Enabling authentication of sliding window queries on streams. In: VLDB (2007)"},{"issue":"4","key":"20_CR28","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. J. ACM\u00a039(4), 859\u2013868 (1992)","journal-title":"J. ACM"},{"key":"20_CR29","unstructured":"Papadopoulos, S., Yang, Y., Papadias, D.: Cads: Continuous authentication on data streams. In: VLDB (2007)"},{"key":"20_CR30","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","author":"A. Razborov","year":"1990","unstructured":"Razborov, A.: On the distributional complexity of disjontness. In: Paterson, M. (ed.) ICALP 1990. LNCS, vol.\u00a0443, Springer, Heidelberg (1990)"},{"issue":"4","key":"20_CR31","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"Shamir, A.: IP = PSPACE. J. ACM\u00a039(4), 869\u2013877 (1992)","journal-title":"J. ACM"},{"key":"20_CR32","unstructured":"Thorup, M., Zhang, Y.: Tabulation based 4-universal hashing with applications to second moment estimation. In: ACM-SIAM SODA (2004)"},{"key":"20_CR33","unstructured":"Tucker, P.A., Maier, D., Delcambre, L.M.L., Sheard, T., Widom, J., Jones, M.P.: Punctuated data streams (2005)"},{"key":"20_CR34","doi-asserted-by":"crossref","unstructured":"Yi, K., Li, F., Hadjieleftheriou, M., Kollios, G., Srivastava, D.: Randomized synopses for query assurance on data streams. In: IEEE ICDE (2008)","DOI":"10.1109\/ICDE.2008.4497450"},{"key":"20_CR35","unstructured":"Zelke, M.: Weighted matching in the semi-streaming model. In: STACS, pp. 669\u2013680 (2008)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02927-1_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T22:02:06Z","timestamp":1685052126000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}