{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:15:44Z","timestamp":1763468144171},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403279"},{"type":"electronic","value":"9783642403286"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_4","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T13:17:34Z","timestamp":1376659054000},"page":"42-57","source":"Crossref","is-referenced-by-count":10,"title":["Approximating Large Frequency Moments with Pick-and-Drop Sampling"],"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":"4_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":"4_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"},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/978-3-642-39206-1_3","volume-title":"ICALP","author":"A. Andoni","year":"2013","unstructured":"Andoni, A., Nguy\u00ea\u0303n, H.L., Polyanskiy, Y., Wu, Y.: Tight lower bound for linear sketches of moments. In: Smotrovs, J., Yakaryilmaz, A. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 25\u201332. Springer, Heidelberg (2013)"},{"issue":"4","key":"4_CR4","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":"4_CR5","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":"4_CR6","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":"4_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 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":"4_CR8","series-title":"LNCS","first-page":"58","volume-title":"APPROX\/RANDOM 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":"4_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":"4_CR10","unstructured":"Braverman, V., Ostrovsky, R.: Recursive sketching for frequency moments. CoRR, abs\/1011.2571 (2010)"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Braverman, V., Ostrovsky, R.: Approximating large frequency moments with pick-and-drop sampling. CoRR, abs\/1212.0202 (2012)","DOI":"10.1007\/978-3-642-40328-6_4"},{"key":"4_CR12","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":"4_CR13","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":"4_CR14","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":"4_CR15","first-page":"205","volume-title":"Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009","author":"K.L. Clarkson","year":"2009","unstructured":"Clarkson, K.L., Woodruff, D.P.: Numerical linear algebra in the streaming model. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 205\u2013214. ACM, New York (2009)"},{"key":"4_CR16","unstructured":"Coppersmith, D., Kumar, R.: An improved data stream algorithm for frequency moments. In: SODA, pp. 151\u2013156 (2004)"},{"issue":"3","key":"4_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":"4_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":"4_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":"4_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":"4_CR21","unstructured":"Ganguly, S.: Polynomial estimators for high frequency moments. CoRR, abs\/1104.4552 (2011)"},{"key":"4_CR22","unstructured":"Ganguly, S.: A lower bound for estimating high moments of a data stream. CoRR, abs\/1201.0253 (2012)"},{"key":"4_CR23","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":"4_CR24","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":"4_CR25","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.: 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":"4_CR26","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":"4_CR27","doi-asserted-by":"crossref","unstructured":"Jayram, T.S., Woodruff, D.: Optimal bounds for johnson-lindenstrauss transforms and streaming problems with sub-constant error. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 1\u201310. SIAM (2011)","DOI":"10.1137\/1.9781611973082.1"},{"key":"4_CR28","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 2st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010 (2010)","DOI":"10.1137\/1.9781611973075.93"},{"key":"4_CR29","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":"4_CR30","doi-asserted-by":"crossref","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)","DOI":"10.1137\/1.9781611973068.46"},{"issue":"2","key":"4_CR31","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1561\/0400000002","volume":"1","author":"S. Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends Theor. Comput. Sci.\u00a01(2), 117\u2013236 (2005)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"4_CR32","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)"},{"issue":"4","key":"4_CR33","doi-asserted-by":"publisher","first-page":"1162","DOI":"10.2307\/1128115","volume":"45","author":"A.D. Pick","year":"1974","unstructured":"Pick, A.D., Frankel, G.W.: A developmental study of strategies of visual selectivity. Child Development\u00a045(4), 1162\u20131165 (1974)","journal-title":"Child Development"},{"key":"4_CR34","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)"},{"key":"4_CR35","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P.: Frequency moments. In: Encyclopedia of Database Systems, pp. 1169\u20131170 (2009)","DOI":"10.1007\/978-0-387-39940-9_167"},{"key":"4_CR36","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/2213977.2214063","volume-title":"Proceedings of the 44th Symposium on Theory of Computing, STOC 2012","author":"D.P. Woodruff","year":"2012","unstructured":"Woodruff, D.P., Zhang, Q.: Tight bounds for distributed functional monitoring. In: Proceedings of the 44th Symposium on Theory of Computing, STOC 2012, pp. 941\u2013960. ACM, New York (2012)"}],"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_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T00:18:01Z","timestamp":1646353081000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}