{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T18:10:02Z","timestamp":1746295802551,"version":"3.40.4"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319087825"},{"type":"electronic","value":"9783319087832"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08783-2_2","type":"book-chapter","created":{"date-parts":[[2014,7,5]],"date-time":"2014-07-05T14:04:30Z","timestamp":1404569070000},"page":"13-24","source":"Crossref","is-referenced-by-count":0,"title":["Sampling from Dense Streams without Penalty"],"prefix":"10.1007","author":[{"given":"Vladimir","family":"Braverman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory","family":"Vorsanger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"2_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":"2_CR2","unstructured":"Babcock, B., Datar, M., Motwani, R.: Sampling from a moving window over streaming data. In: SODA, pp. 633\u2013634 (2002)"},{"key":"2_CR3","unstructured":"Bar-Yossef, Z.: The complexity of massive data set computations. PhD thesis, Berkeley, CA, USA, AAI3183783 (2002)"},{"issue":"4","key":"2_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":"2_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":"2_CR6","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1109\/ICDEW.2007.4401052","volume-title":"Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering Workshop, ICDEW 2007","author":"S. Bhattacharyya","year":"2007","unstructured":"Bhattacharyya, S., Madeira, A., Muthukrishnan, S., Ye, T.: How to scalably and accurately skip past streams. In: Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering Workshop, ICDEW 2007, pp. 654\u2013663. IEEE Computer Society, Washington, DC (2007)"},{"key":"2_CR7","unstructured":"Braverman, V., Katzman, J., Seidell, C., Vorsanger, G.: Approximating large frequency moments with o(n 1\u2009\u2212\u20092\/k ) bits. CoRR, abs\/1401.1763 (2014)"},{"key":"2_CR8","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":"2_CR9","doi-asserted-by":"crossref","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":"2_CR10","doi-asserted-by":"crossref","unstructured":"Braverman, V., Ostrovsky, R.: Approximating large frequency moments with pick-and-drop sampling. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) APPROX\/RANDOM 2013. LNCS, vol.\u00a08096, pp. 42\u201357. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-40328-6_4"},{"key":"2_CR11","doi-asserted-by":"crossref","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)","DOI":"10.1007\/978-3-642-40328-6_5"},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-642-39206-1_21","volume-title":"Automata, Languages, and Programming","author":"V. Braverman","year":"2013","unstructured":"Braverman, V., Ostrovsky, R., Vilenchik, D.: How hard is counting triangles in the streaming model? In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 244\u2013254. Springer, Heidelberg (2013)"},{"key":"2_CR13","unstructured":"Braverman, V., Ostrovsky, R., Vorsanger, G.: Weighted sampling without replacement from data streams (2013) (submitted)"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Braverman, V., Ostrovsky, R., Zaniolo, C.: Optimal sampling from sliding windows. In: PODS, pp. 147\u2013156 (2009)","DOI":"10.1145\/1559795.1559818"},{"key":"2_CR15","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 Conference on Computational Complexity, pp. 107\u2013117 (2003)","DOI":"10.1109\/CCC.2003.1214414"},{"key":"2_CR16","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1145\/304182.304206","volume-title":"Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, SIGMOD 1999","author":"S. Chaudhuri","year":"1999","unstructured":"Chaudhuri, S., Motwani, R., Narasayya, V.: On random sampling over joins. In: Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data, SIGMOD 1999, pp. 263\u2013274. ACM, New York (1999)"},{"key":"2_CR17","unstructured":"Coppersmith, D., Kumar, R.: An improved data stream algorithm for frequency moments. In: SODA, pp. 151\u2013156 (2004)"},{"issue":"3","key":"2_CR18","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":"2_CR19","first-page":"501","volume-title":"FOCS 1999: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS 1999","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, FOCS 1999, p. 501. IEEE Computer Society, Washington, DC (1999)"},{"key":"2_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":"2_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. LNCS, vol.\u00a04627, pp. 479\u2013493. Springer, Heidelberg (2007)"},{"key":"2_CR22","doi-asserted-by":"crossref","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":"2_CR23","doi-asserted-by":"crossref","unstructured":"Johnson, N.L., Kemp, A.W., Kotz, S.: Univariate discrete distributions. Wiley-Interscience (2005)","DOI":"10.1002\/0471715816"},{"key":"2_CR24","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":"2_CR25","doi-asserted-by":"crossref","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":"2_CR26","unstructured":"Knuth, D.E.: The art of computer programming, fundamental algorithms, 3rd edn., vol.\u00a01. Addison Wesley Longman Publishing Co., Inc., Redwood City (1997)"},{"key":"2_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":"2_CR28","unstructured":"McGregor, A.: Open problems in data streams and related topics. In: IITK Workshop on Algorithms for Data Streams (2006), http:\/\/www.cse.iitk.ac.in\/users\/sganguly\/data-stream-probs.pdf (2007)"},{"key":"2_CR29","first-page":"273","volume-title":"Proceedings of the 31st Symposium on Principles of Database Systems, PODS 2012","author":"A. McGregor","year":"2012","unstructured":"McGregor, A., Pavan, A., Tirthapura, S., Woodruff, D.: Space-efficient estimation of statistics over sub-sampled streams. In: Proceedings of the 31st Symposium on Principles of Database Systems, PODS 2012, pp. 273\u2013282. ACM, New York (2012)"},{"key":"2_CR30","first-page":"381","volume-title":"Proceedings of the 2009 IEEE International Conference on Data Engineering, ICDE 2009","author":"F. Rusu","year":"2009","unstructured":"Rusu, F., Dobra, A.: Sketching sampled data streams. In: Proceedings of the 2009 IEEE International Conference on Data Engineering, ICDE 2009, pp. 381\u2013392. IEEE Computer Society, Washington, DC (2009)"},{"key":"2_CR31","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer-Verlag New York, Inc., New York (2001)"},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Vitter, J.S.: ACM Transactions on Mathematical Software, 11(1), 37\u201357","DOI":"10.1145\/3147.3165"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08783-2_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T17:49:11Z","timestamp":1746294551000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08783-2_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319087825","9783319087832"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08783-2_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}