{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T09:35:05Z","timestamp":1774949705219,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642403279","type":"print"},{"value":"9783642403286","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_5","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T09:17:34Z","timestamp":1376644654000},"page":"58-70","source":"Crossref","is-referenced-by-count":26,"title":["Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams"],"prefix":"10.1007","author":[{"given":"Vladimir","family":"Braverman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"5_CR1","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. J. Comput. Syst. Sci.\u00a058(1), 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Andoni, A., Krauthgamer, R., Onak, K.: Streaming algorithms via precision sampling. In: FOCS, pp. 363\u2013372 (2011)","DOI":"10.1109\/FOCS.2011.82"},{"issue":"4","key":"5_CR3","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","volume":"68","author":"Z. Bar-Yossef","year":"2004","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci.\u00a068(4), 702\u2013732 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45726-7_1","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"Z. Bar-Yossef","year":"2002","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D., Trevisan, L.: Counting distinct elements in a data stream. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 1\u201310. Springer, Heidelberg (2002)"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1145\/1250790.1250891","volume-title":"STOC 2007: Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing","author":"P. Beame","year":"2007","unstructured":"Beame, P., Jayram, T.S., Rudra, A.: Lower bounds for randomized read\/write stream algorithms. In: STOC 2007: Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, pp. 689\u2013698. ACM, New York (2007)"},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"Bhuvanagiri, L., Ganguly, S., Kesh, D., Saha, C.: Simpler algorithm for estimating frequency moments of data streams. In: SODA, pp. 708\u2013713 (2006)","DOI":"10.1145\/1109557.1109634"},{"key":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/978-3-642-38768-5_56","volume-title":"Computing and Combinatorics","author":"V. Braverman","year":"2013","unstructured":"Braverman, V., Gelles, R., Ostrovsky, R.: How to catch l\n                  2-heavy-hitters on sliding windows. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol.\u00a07936, pp. 638\u2013650. Springer, Heidelberg (2013)"},{"key":"5_CR8","series-title":"LNCS","first-page":"58","volume-title":"Approx 2013","author":"V. Braverman","year":"2013","unstructured":"Braverman, V., Ostrovsky, R.: Generalizing the layering method of indyk and woodruff: Recursive sketches for frequency-based vectors on streams. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) APPROX\/RANDOM 2013. LNCS, vol.\u00a08096, pp. 58\u201370. Springer, Heidelberg (2013)"},{"key":"5_CR9","first-page":"283","volume-title":"Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007","author":"V. Braverman","year":"2007","unstructured":"Braverman, V., Ostrovsky, R.: Smooth histograms for sliding windows. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007, pp. 283\u2013293. IEEE Computer Society, Washington, DC (2007)"},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1145\/1806689.1806728","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010","author":"V. Braverman","year":"2010","unstructured":"Braverman, V., Ostrovsky, R.: Measuring independence of datasets. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 271\u2013280. ACM, New York (2010)"},{"key":"5_CR11","unstructured":"Braverman, V., Ostrovsky, R.: Recursive sketching for frequency moments. CoRR, abs\/1011.2571 (2010)"},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1145\/1806689.1806729","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010","author":"V. Braverman","year":"2010","unstructured":"Braverman, V., Ostrovsky, R.: Zero-one frequency laws. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 281\u2013290. ACM, New York (2010)"},{"key":"5_CR13","first-page":"641","volume-title":"STOC 2008: Proceedings of the 40th Annual ACM Symposium on Theory of Computing","author":"A. Chakrabarti","year":"2008","unstructured":"Chakrabarti, A., Cormode, G., McGregor, A.: Robust lower bounds for communication and stream computation. In: STOC 2008: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 641\u2013650. ACM, New York (2008)"},{"key":"5_CR14","unstructured":"Chakrabarti, A., Khot, S., Sun, X.: Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In: IEEE Conference on Computational Complexity, pp. 107\u2013117 (2003)"},{"key":"5_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/3-540-45465-9_59","volume-title":"Automata, Languages and Programming","author":"M. Charikar","year":"2002","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 693\u2013703. Springer, Heidelberg (2002)"},{"key":"5_CR16","unstructured":"Coppersmith, D., Kumar, R.: An improved data stream algorithm for frequency moments. In: SODA, pp. 151\u2013156 (2004)"},{"issue":"3","key":"5_CR17","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1109\/TKDE.2003.1198388","volume":"15","author":"G. Cormode","year":"2003","unstructured":"Cormode, G., Datar, M., Indyk, P., Muthukrishnan, S.: Comparing data streams using hamming norms (how to zero in). IEEE Trans. on Knowl. and Data Eng.\u00a015(3), 529\u2013540 (2003)","journal-title":"IEEE Trans. on Knowl. and Data Eng."},{"key":"5_CR18","first-page":"501","volume-title":"FOCS 1999: Proceedings of the 40th Annual Symposium on Foundations of Computer Science","author":"J. Feigenbaum","year":"1999","unstructured":"Feigenbaum, J., Kannan, S., Strauss, M., Viswanathan, M.: An approximate l1-difference algorithm for massive data streams. In: FOCS 1999: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p. 501. IEEE Computer Society, Washington, DC (1999)"},{"issue":"2","key":"5_CR19","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0022-0000(85)90041-8","volume":"31","author":"P. Flajolet","year":"1985","unstructured":"Flajolet, P., Nigel Martin, G.: Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci.\u00a031(2), 182\u2013209 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-540-27821-4_33","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Ganguly","year":"2004","unstructured":"Ganguly, S.: Estimating frequency moments of data streams using random linear combinations. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) APPROX and RANDOM 2004. LNCS, vol.\u00a03122, pp. 369\u2013380. Springer, Heidelberg (2004)"},{"key":"5_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/978-3-540-74208-1_35","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Ganguly","year":"2007","unstructured":"Ganguly, S., Cormode, G.: On estimating frequency moments of data streams. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX and RANDOM 2007. LNCS, vol.\u00a04627, pp. 479\u2013493. Springer, Heidelberg (2007)"},{"issue":"3","key":"5_CR22","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1145\/1147954.1147955","volume":"53","author":"P. Indyk","year":"2006","unstructured":"Indyk, P.: Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM\u00a053(3), 307\u2013323 (2006)","journal-title":"J. ACM"},{"key":"5_CR23","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/1060590.1060621","volume-title":"STOC 2005: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing","author":"P. Indyk","year":"2005","unstructured":"Indyk, P., Woodruff, D.L.P.: Optimal approximations of the frequency moments of data streams. In: STOC 2005: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, pp. 202\u2013208. ACM, New York (2005)"},{"key":"5_CR24","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1145\/1265530.1265565","volume-title":"PODS 2007: Proceedings of the Twenty-sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems","author":"T.S. Jayram","year":"2007","unstructured":"Jayram, T.S., McGregor, A., Muthukrishnan, S., Vee, E.: Estimating statistical aggregates on probabilistic data streams. In: PODS 2007: Proceedings of the Twenty-sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 243\u2013252. ACM, New York (2007)"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.P.: On the exact space complexity of sketching and streaming small norms. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010 (2010)","DOI":"10.1137\/1.9781611973075.93"},{"key":"5_CR26","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1807085.1807094","volume-title":"PODS 2010: Proceedings of the Twenty-ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems of Data","author":"D.M. Kane","year":"2010","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.P.: An optimal algorithm for the distinct elements problem. In: PODS 2010: Proceedings of the Twenty-ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems of Data, pp. 41\u201352. ACM, New York (2010)"},{"key":"5_CR27","first-page":"412","volume-title":"SODA 2009: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"P. Li","year":"2009","unstructured":"Li, P.: Compressed counting. In: SODA 2009: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 412\u2013421. Society for Industrial and Applied Mathematics, Philadelphia (2009)"},{"key":"5_CR28","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/1807085.1807101","volume-title":"PODS 2010: Proceedings of the Twenty-ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems of Data","author":"J. Nelson","year":"2010","unstructured":"Nelson, J., Woodruff, D.P.: Fast manhattan sketches in data streams. In: PODS 2010: Proceedings of the Twenty-ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems of Data, pp. 99\u2013110. ACM, New York (2010)"},{"key":"5_CR29","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1145\/2213556.2213595","volume-title":"Proceedings of the 31st Symposium on Principles of Database Systems, PODS 2012","author":"S. Tirthapura","year":"2012","unstructured":"Tirthapura, S., Woodruff, D.P.: Rectangle-efficient aggregation in spatial data streams. In: Proceedings of the 31st Symposium on Principles of Database Systems, PODS 2012, pp. 283\u2013294. ACM, New York (2012)"},{"key":"5_CR30","unstructured":"Woodruff, D.P.: Optimal space lower bounds for all frequency moments. In: SODA 2004: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 167\u2013175 (2004)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40328-6_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T13:50:42Z","timestamp":1558014642000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}