{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:43Z","timestamp":1778807863504,"version":"3.51.4"},"reference-count":79,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,6,24]],"date-time":"2023-06-24T00:00:00Z","timestamp":1687564800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,7,31]]},"abstract":"\n One of the oldest problems in the data stream model is to approximate the\n p<\/jats:italic>\n th moment\n \n \\(\\Vert \\mathbf {X}\\Vert _p^p = \\sum _{i=1}^n \\mathbf {X}_i^p\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n of an underlying non-negative vector\n \n \\(\\mathbf {X}\\in \\mathbb {R}^n\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , which is presented as a sequence of\n \n \\(\\mathrm{poly}(n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n updates to its coordinates. Of particular interest is when\n \n \\(p \\in (0,2]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Although a tight space bound of\n \n \\(\\Theta (\\epsilon ^{-2} \\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits is known for this problem when both positive and negative updates are allowed, surprisingly, there is still a gap in the space complexity of this problem when all updates are positive. Specifically, the upper bound is\n \n \\(O(\\epsilon ^{-2} \\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits, while the lower bound is only\n \n \\(\\Omega (\\epsilon ^{-2} + \\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits. Recently, an upper bound of\n \n \\(\\tilde{O}(\\epsilon ^{-2} + \\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits was obtained under the assumption that the updates arrive in a\n random order<\/jats:italic>\n .\n <\/jats:p>\n \n We show that for\n \n \\(p \\in (0, 1]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , the random order assumption is not needed. Namely, we give an upper bound for worst-case streams of\n \n \\(\\tilde{O}(\\epsilon ^{-2} + \\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits for estimating\n \n \\(\\Vert \\mathbf {X}\\Vert _p^p\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Our techniques also give new upper bounds for estimating the empirical entropy in a stream. However, we show that for\n \n \\(p \\in (1,2]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , in the natural coordinator and blackboard distributed communication topologies, there is an\n \n \\(\\tilde{O}(\\epsilon ^{-2})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bit max-communication upper bound based on a randomized rounding scheme. Our protocols also give rise to protocols for heavy hitters and approximate matrix product. We generalize our results to arbitrary communication topologies\n G<\/jats:italic>\n , obtaining an\n \n \\(\\tilde{O}(\\epsilon ^{2} \\log d)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n max-communication upper bound, where\n d<\/jats:italic>\n is the diameter of\n G<\/jats:italic>\n . Interestingly, our upper bound rules out natural communication complexity-based approaches for proving an\n \n \\(\\Omega (\\epsilon ^{-2} \\log n)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bit lower bound for\n \n \\(p \\in (1,2]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for streaming algorithms. In particular, any such lower bound must come from a topology with large diameter.\n <\/jats:p>","DOI":"10.1145\/3596494","type":"journal-article","created":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T12:32:32Z","timestamp":1683721952000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Towards Optimal Moment Estimation in Streaming and Distributed Models"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0332-6332","authenticated-orcid":false,"given":"Rajesh","family":"Jayaram","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2158-1380","authenticated-orcid":false,"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,24]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"http:\/\/hadoop.apache.org\/. (n. d.). Retrieved from http:\/\/hadoop.apache.org\/."},{"key":"e_1_3_2_3_2","unstructured":"https:\/\/spark.apache.org\/. (n. d.). Retrieved from https:\/\/spark.apache.org\/"},{"key":"e_1_3_2_4_2","first-page":"20","volume-title":"Proceedings of the 28th Annual ACM Symposium on Theory of Computing","author":"Alon Noga","year":"1996","unstructured":"Noga Alon, Yossi Matias, and Mario Szegedy. 1996. The space complexity of approximating the frequency moments. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing. ACM, 20\u201329."},{"key":"e_1_3_2_5_2","first-page":"363","volume-title":"Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science","author":"Andoni Alexandr","year":"2011","unstructured":"Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. 2011. Streaming algorithms via precision sampling. In Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science. IEEE, 363\u2013372."},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/978-3-642-02927-1_10","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming","author":"Arackaparambil Chrisil","year":"2009","unstructured":"Chrisil Arackaparambil, Joshua Brody, and Amit Chakrabarti. 2009. Functional monitoring without monotonicity. In Proceedings of the International Colloquium on Automata, Languages, and Programming. Springer, 95\u2013106."},{"key":"e_1_3_2_7_2","first-page":"1","volume-title":"Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems","author":"Babcock Brian","year":"2002","unstructured":"Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, and Jennifer Widom. 2002. Models and issues in data stream systems. In Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. ACM, 1\u201316."},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1145\/2939672.2939796","volume-title":"Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Balcan Maria Florina","year":"2016","unstructured":"Maria Florina Balcan, Yingyu Liang, Le Song, David Woodruff, and Bo Xie. 2016. Communication efficient distributed kernel principal component analysis. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 725\u2013734."},{"issue":"4","key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","article-title":"An information statistics approach to data stream and communication complexity","volume":"68","author":"Bar-Yossef Ziv","year":"2004","unstructured":"Ziv Bar-Yossef, Thathachar S. Jayram, Ravi Kumar, and D. Sivakumar. 2004. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci. 68, 4 (2004), 702\u2013732.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_3_2_10_2","first-page":"902","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Bhojanapalli Srinadh","year":"2015","unstructured":"Srinadh Bhojanapalli, Prateek Jain, and Sujay Sanghavi. 2015. Tighter low-rank approximation via sampling the leveraged element. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 902\u2013920."},{"key":"e_1_3_2_11_2","article-title":"Continuous monitoring of lp norms in data streams","author":"B\u0142asiok Jaros\u0142aw","year":"2017","unstructured":"Jaros\u0142aw B\u0142asiok, Jian Ding, and Jelani Nelson. 2017. Continuous monitoring of lp norms in data streams. arXiv preprint arXiv:1704.06710 (2017).","journal-title":"arXiv preprint arXiv:1704.06710"},{"key":"e_1_3_2_12_2","first-page":"236","volume-title":"Proceedings of the 48th Annual ACM Symposium on Theory of Computing","author":"Boutsidis Christos","year":"2016","unstructured":"Christos Boutsidis, David P. Woodruff, and Peilin Zhong. 2016. Optimal principal component analysis in distributed and streaming models. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing. ACM, 236\u2013249."},{"key":"e_1_3_2_13_2","first-page":"668","volume-title":"Proceedings of the IEEE 54th Annual Symposium on Foundations of Computer Science","author":"Braverman Mark","year":"2013","unstructured":"Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, and Vinod Vaikuntanathan. 2013. A tight bound for set disjointness in the message-passing model. In Proceedings of the IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE, 668\u2013677."},{"key":"e_1_3_2_14_2","volume-title":"Proceedings of the IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)","author":"Braverman Mark","year":"2020","unstructured":"Mark Braverman, Sumegha Garg, and David Woodruff. 2020. The coin problem with applications to data streams. In Proceedings of the IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_15_2","article-title":"BPTree: An L2 heavy hitters algorithm using constant memory","author":"Braverman Vladimir","year":"2016","unstructured":"Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David P. Woodruff. 2016. BPTree: An L2 heavy hitters algorithm using constant memory. arXiv preprint arXiv:1603.00759 (2016).","journal-title":"arXiv preprint arXiv:1603.00759"},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/2902251.2902282","volume-title":"Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Braverman Vladimir","year":"2016","unstructured":"Vladimir Braverman, Stephen R. Chestnut, David P. Woodruff, and Lin F. Yang. 2016. Streaming space complexity of nearly all functions of one variable on frequency vectors. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 261\u2013276."},{"key":"e_1_3_2_17_2","volume-title":"Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201914)","author":"Braverman Vladimir","year":"2014","unstructured":"Vladimir Braverman, Jonathan Katzman, Charles Seidell, and Gregory Vorsanger. 2014. An optimal algorithm for large frequency moments using O (n^2303(1-2\/k)) bits. In Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201914). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_18_2","article-title":"Recursive sketching for frequency moments","author":"Braverman Vladimir","year":"2010","unstructured":"Vladimir Braverman and Rafail Ostrovsky. 2010. Recursive sketching for frequency moments. arXiv preprint arXiv:1011.2571 (2010).","journal-title":"arXiv preprint arXiv:1011.2571"},{"key":"e_1_3_2_19_2","article-title":"Revisiting frequency moment estimation in random order streams","author":"Braverman Vladimir","year":"2018","unstructured":"Vladimir Braverman, Emanuele Viola, David Woodruff, and Lin F. Yang. 2018. Revisiting frequency moment estimation in random order streams. arXiv preprint arXiv:1803.02270 (2018).","journal-title":"arXiv preprint arXiv:1803.02270"},{"issue":"3","key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1798596.1798604","article-title":"A near-optimal algorithm for estimating the entropy of a stream","volume":"6","author":"Chakrabarti Amit","year":"2010","unstructured":"Amit Chakrabarti, Graham Cormode, and Andrew McGregor. 2010. A near-optimal algorithm for estimating the entropy of a stream. ACM Trans. Algor. 6, 3 (2010), 1\u201321.","journal-title":"ACM Trans. Algor."},{"issue":"1","key":"e_1_3_2_21_2","first-page":"1","article-title":"Robust lower bounds for communication and stream computation","volume":"12","author":"Chakrabarti Amit","year":"2016","unstructured":"Amit Chakrabarti, Graham Cormode, and Andrew McGregor. 2016. Robust lower bounds for communication and stream computation. Theory Comput. 12, 1 (2016), 1\u201335.","journal-title":"Theory Comput."},{"key":"e_1_3_2_22_2","first-page":"107","volume-title":"Proceedings of the 18th IEEE Annual Conference on Computational Complexity.","author":"Chakrabarti Amit","year":"2003","unstructured":"Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. 2003. Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In Proceedings of the 18th IEEE Annual Conference on Computational Complexity. IEEE, 107\u2013117."},{"issue":"5","key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1137\/120861072","article-title":"An optimal lower bound on the communication complexity of gap-Hamming-distance","volume":"41","author":"Chakrabarti Amit","year":"2012","unstructured":"Amit Chakrabarti and Oded Regev. 2012. An optimal lower bound on the communication complexity of gap-Hamming-distance. SIAM J. Comput. 41, 5 (2012), 1299\u20131317.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","unstructured":"Moses Charikar Kevin Chen and Martin Farach-Colton. 2002. Finding frequent items in data streams. In Automata Languages and Programming: 29th International Colloquium (ICALP\u201902) . Springer Berlin Heidelberg.","DOI":"10.1007\/3-540-45465-9_59"},{"key":"e_1_3_2_25_2","first-page":"631","volume-title":"Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science","author":"Chattopadhyay Arkadev","year":"2014","unstructured":"Arkadev Chattopadhyay, Jaikumar Radhakrishnan, and Atri Rudra. 2014. Topology matters in communication. In Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE, 631\u2013640."},{"key":"e_1_3_2_26_2","first-page":"3727","volume-title":"Proceedings of the International Conference on Advances in Neural Information Processing Systems","author":"Chen Jiecao","year":"2016","unstructured":"Jiecao Chen, He Sun, David Woodruff, and Qin Zhang. 2016. Communication-optimal distributed clustering. In Proceedings of the International Conference on Advances in Neural Information Processing Systems. 3727\u20133735."},{"key":"e_1_3_2_27_2","unstructured":"Peter Clifford and Ioana Cosma. 2013. A simple sketching algorithm for entropy estimation over streaming data. Artificial Intelligence and Statistics . PMLR."},{"key":"e_1_3_2_28_2","unstructured":"Edith Cohen. 2013. TAU CS 0368.3239 Leveraging Big Data Lecture Notes. (Fall2013)."},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1145\/3097983.3098020","volume-title":"Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Cohen Edith","year":"2017","unstructured":"Edith Cohen. 2017. HyperLogLog hyperextended: Sketches for concave sublinear frequency statistics. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 105\u2013114."},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1109\/ICDE.2002.994778","volume-title":"Proceedings of the 18th International Conference on Data Engineering","author":"Cormode Graham","year":"2002","unstructured":"Graham Cormode, Piotr Indyk, Nick Koudas, and S. Muthukrishnan. 2002. Fast mining of massive tabular data via approximate distance computations. In Proceedings of the 18th International Conference on Data Engineering. IEEE, 605\u2013614."},{"issue":"1","key":"e_1_3_2_31_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3297715","article-title":"Lp samplers and their applications: A survey","volume":"52","author":"Cormode Graham","year":"2019","unstructured":"Graham Cormode and Hossein Jowhari. 2019. Lp samplers and their applications: A survey. ACM Comput. Surv. 52, 1 (2019), 1\u201331.","journal-title":"ACM Comput. Surv."},{"key":"e_1_3_2_32_2","first-page":"25","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases","author":"Cormode Graham","year":"2005","unstructured":"Graham Cormode, S. Muthukrishnan, and Irina Rozenbaum. 2005. Summarizing and mining inverse distributions on data streams via dynamic inverse sampling. In Proceedings of the 31st International Conference on Very Large Data Bases. VLDB Endowment, 25\u201336."},{"issue":"2","key":"e_1_3_2_33_2","first-page":"21","article-title":"Algorithms for distributed functional monitoring","volume":"7","author":"Cormode Graham","year":"2011","unstructured":"Graham Cormode, S. Muthukrishnan, and Ke Yi. 2011. Algorithms for distributed functional monitoring. ACM Trans. Algor. 7, 2 (2011), 21.","journal-title":"ACM Trans. Algor."},{"key":"e_1_3_2_34_2","first-page":"1434","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Feldman Dan","year":"2013","unstructured":"Dan Feldman, Melanie Schmidt, and Christian Sohler. 2013. Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 1434\u20131453."},{"issue":"1","key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF01934993","article-title":"Approximate counting: A detailed analysis","volume":"25","author":"Flajolet Philippe","year":"1985","unstructured":"Philippe Flajolet. 1985. Approximate counting: A detailed analysis. BIT Numer. Math. 25, 1 (1985), 113\u2013134.","journal-title":"BIT Numer. Math."},{"key":"e_1_3_2_36_2","first-page":"707","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Ghashami Mina","year":"2014","unstructured":"Mina Ghashami and Jeff M. Phillips. 2014. Relative errors for deterministic low-rank matrix approximations. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 707\u2013717."},{"key":"e_1_3_2_37_2","first-page":"331","volume-title":"ACM SIGMOD Record","author":"Gibbons Phillip B.","year":"1998","unstructured":"Phillip B. Gibbons and Yossi Matias. 1998. New sampling-based summary statistics for improving approximate query answers. In ACM SIGMOD Record, Vol. 27. ACM, 331\u2013342."},{"key":"e_1_3_2_38_2","unstructured":"Phillip B. Gibbons Yossi Matias and Viswanath Poosala. Fast incremental maintenance of approximate histograms."},{"key":"e_1_3_2_39_2","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1016\/B978-155860869-6\/50047-0","volume-title":"Proceedings of the 28th International Conference on Very Large Databases","author":"Gilbert Anna C.","year":"2002","unstructured":"Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, and Martin J. Strauss. 2002. How to summarize the universe: Dynamic maintenance of quantiles. In Proceedings of the 28th International Conference on Very Large Databases. Elsevier, 454\u2013465."},{"key":"e_1_3_2_40_2","article-title":"Asymptotically optimal lower bounds on the NIH-multi-party information","author":"Gronemeier Andre","year":"2009","unstructured":"Andre Gronemeier. 2009. Asymptotically optimal lower bounds on the NIH-multi-party information. arXiv preprint arXiv:0902.1609 (2009).","journal-title":"arXiv preprint arXiv:0902.1609"},{"key":"e_1_3_2_41_2","first-page":"489","volume-title":"Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science","author":"Harvey Nicholas J. A.","year":"2008","unstructured":"Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak. 2008. Sketching and streaming entropy via approximation theory. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 489\u2013498."},{"key":"e_1_3_2_42_2","first-page":"227","volume-title":"Proceedings of the IEEE Information Theory Workshop","author":"Harvey Nicholas J. A.","year":"2008","unstructured":"Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak. 2008. Streaming algorithms for estimating entropy. In Proceedings of the IEEE Information Theory Workshop. IEEE, 227\u2013231."},{"key":"e_1_3_2_43_2","first-page":"134","volume-title":"Proceedings of the 26th IEEE International Conference on Computer Communications","author":"Huang Ling","year":"2007","unstructured":"Ling Huang, XuanLong Nguyen, Minos Garofalakis, Joseph M. Hellerstein, Michael I. Jordan, Anthony D. Joseph, and Nina Taft. 2007. Communication-efficient online detection of network-wide anomalies. In Proceedings of the 26th IEEE International Conference on Computer Communications. IEEE, 134\u2013142."},{"key":"e_1_3_2_44_2","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1145\/2213556.2213596","volume-title":"Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Huang Zengfeng","year":"2012","unstructured":"Zengfeng Huang, Ke Yi, and Qin Zhang. 2012. Randomized algorithms for tracking distributed count, frequencies, and ranks. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. ACM, 295\u2013306."},{"issue":"3","key":"e_1_3_2_45_2","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1145\/1147954.1147955","article-title":"Stable distributions, pseudorandom generators, embeddings, and data stream computation","volume":"53","author":"Indyk Piotr","year":"2006","unstructured":"Piotr Indyk. 2006. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM 53, 3 (2006), 307\u2013323.","journal-title":"J. ACM"},{"key":"e_1_3_2_46_2","first-page":"202","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing","author":"Indyk Piotr","year":"2005","unstructured":"Piotr Indyk and David Woodruff. 2005. Optimal approximations of the frequency moments of data streams. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, 202\u2013208."},{"key":"e_1_3_2_47_2","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1145\/3294052.3319696","volume-title":"Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Jayaram Rajesh","year":"2019","unstructured":"Rajesh Jayaram, Gokarna Sharma, Srikanta Tirthapura, and David P. Woodruff. 2019. Weighted reservoir sampling from distributed streams. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 218\u2013235."},{"key":"e_1_3_2_48_2","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/3196959.3196986","volume-title":"Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Jayaram Rajesh","year":"2018","unstructured":"Rajesh Jayaram and David P. Woodruff. 2018. Data streams with bounded deletions. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 341\u2013354."},{"key":"e_1_3_2_49_2","first-page":"544","volume-title":"Proceedings of the IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Jayaram Rajesh","year":"2018","unstructured":"Rajesh Jayaram and David P. Woodruff. 2018. PerfectLp sampling in a data stream. In Proceedings of the IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 544\u2013555."},{"key":"e_1_3_2_50_2","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1007\/978-3-642-03685-9_42","volume-title":"Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Jayram T. S.","year":"2009","unstructured":"T. S. Jayram. 2009. Hellinger strikes back: A note on the multi-party information complexity of AND. In Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 562\u2013573."},{"issue":"1","key":"e_1_3_2_51_2","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4086\/toc.2008.v004a006","article-title":"The one-way communication complexity of Hamming distance.","volume":"4","author":"Jayram Thathachar S.","year":"2008","unstructured":"Thathachar S. Jayram, Ravi Kumar, and D. Sivakumar. 2008. The one-way communication complexity of Hamming distance. Theor. Comput. 4, 1 (2008), 129\u2013135.","journal-title":"Theor. Comput."},{"key":"e_1_3_2_52_2","first-page":"765","volume-title":"Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science","author":"Jayram Thathachar S.","year":"2009","unstructured":"Thathachar S. Jayram and David P. Woodruff. 2009. The data stream space complexity of cascaded norms. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 765\u2013774."},{"key":"e_1_3_2_53_2","first-page":"49","volume-title":"Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS\u201911)","author":"Jowhari Hossein","year":"2011","unstructured":"Hossein Jowhari, Mert Sa\u011flam, and G\u00e1bor Tardos. 2011. Tight bounds for Lp samplers, finding duplicates in streams, and related problems. In Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS\u201911). ACM, New York, NY, 49\u201358. DOI:10.1145\/1989284.1989289."},{"issue":"5","key":"e_1_3_2_54_2","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1145\/635506.605408","article-title":"Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with ZebraNet","volume":"30","author":"Juang Philo","year":"2002","unstructured":"Philo Juang, Hidekazu Oki, Yong Wang, Margaret Martonosi, Li Shiuan Peh, and Daniel Rubenstein. 2002. Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with ZebraNet. ACM SIGARCH Comput. Archit. News 30, 5 (2002), 96\u2013107.","journal-title":"ACM SIGARCH Comput. Archit. News"},{"issue":"1","key":"e_1_3_2_55_2","first-page":"4","article-title":"Sparser Johnson-Lindenstrauss transforms","volume":"61","author":"Kane Daniel M.","year":"2014","unstructured":"Daniel M. Kane and Jelani Nelson. 2014. Sparser Johnson-Lindenstrauss transforms. J. ACM 61, 1 (2014), 4.","journal-title":"J. ACM"},{"key":"e_1_3_2_56_2","first-page":"745","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing","author":"Kane Daniel M.","year":"2011","unstructured":"Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff. 2011. Fast moment estimation in data streams in optimal space. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing. ACM, 745\u2013754."},{"key":"e_1_3_2_57_2","first-page":"1161","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Kane Daniel M.","year":"2010","unstructured":"Daniel M. Kane, Jelani Nelson, and David P. Woodruff. 2010. On the exact space complexity of sketching and streaming small norms. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1161\u20131178."},{"key":"e_1_3_2_58_2","first-page":"1040","volume-title":"Proceedings of the Conference on Learning Theory","author":"Kannan Ravi","year":"2014","unstructured":"Ravi Kannan, Santosh Vempala, and David Woodruff. 2014. Principal component analysis and higher correlations for distributed data. In Proceedings of the Conference on Learning Theory. 1040\u20131057."},{"key":"e_1_3_2_59_2","article-title":"Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams","author":"Kapralov Michael","year":"2017","unstructured":"Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, and Mobin Yahyazadeh. 2017. Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams. arXiv preprint arXiv:1704.00633 (2017).","journal-title":"arXiv preprint arXiv:1704.00633"},{"key":"e_1_3_2_60_2","first-page":"412","volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Li Ping","year":"2009","unstructured":"Ping Li. 2009. Compressed counting. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 412\u2013421."},{"key":"e_1_3_2_61_2","first-page":"477","volume-title":"Proceedings of the 24th Annual Conference on Learning Theory","author":"Li Ping","year":"2011","unstructured":"Ping Li and Cun-Hui Zhang. 2011. A new algorithm for compressed counting with applications in Shannon entropy estimation in dynamic data. In Proceedings of the 24th Annual Conference on Learning Theory. 477\u2013496."},{"key":"e_1_3_2_62_2","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1007\/978-3-642-40328-6_43","volume-title":"Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Li Yi","year":"2013","unstructured":"Yi Li and David P. Woodruff. 2013. A tight lower bound for high frequency moment estimation with small error. In Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 623\u2013638."},{"key":"e_1_3_2_63_2","first-page":"3113","volume-title":"Proceedings of the International Conference on Advances in Neural Information Processing Systems","author":"Liang Yingyu","year":"2014","unstructured":"Yingyu Liang, Maria-Florina F. Balcan, Vandana Kanchanapally, and David Woodruff. 2014. Improved distributed principal component analysis. In Proceedings of the International Conference on Advances in Neural Information Processing Systems. 3113\u20133121."},{"key":"e_1_3_2_64_2","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1145\/2487575.2487623","volume-title":"Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Liberty Edo","year":"2013","unstructured":"Edo Liberty. 2013. Simple and deterministic matrix sketching. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 581\u2013588."},{"issue":"1","key":"e_1_3_2_65_2","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1145\/1061318.1061322","article-title":"TinyDB: An acquisitional query processing system for sensor networks","volume":"30","author":"Madden Samuel R.","year":"2005","unstructured":"Samuel R. Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. 2005. TinyDB: An acquisitional query processing system for sensor networks. ACM Trans. Datab. Syst. 30, 1 (2005), 122\u2013173.","journal-title":"ACM Trans. Datab. Syst."},{"issue":"2","key":"e_1_3_2_66_2","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1007\/s00453-015-9974-0","article-title":"Space-efficient estimation of statistics over sub-sampled streams","volume":"74","author":"McGregor Andrew","year":"2016","unstructured":"Andrew McGregor, A. Pavan, Srikanta Tirthapura, and David P. Woodruff. 2016. Space-efficient estimation of statistics over sub-sampled streams. Algorithmica 74, 2 (2016), 787\u2013811.","journal-title":"Algorithmica"},{"key":"e_1_3_2_67_2","first-page":"1143","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Monemizadeh Morteza","year":"2010","unstructured":"Morteza Monemizadeh and David P. Woodruff. 2010. 1-pass relative-error lp-sampling with applications. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1143\u20131160."},{"issue":"10","key":"e_1_3_2_68_2","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1145\/359619.359627","article-title":"Counting large numbers of events in small registers","volume":"21","author":"Morris Robert","year":"1978","unstructured":"Robert Morris. 1978. Counting large numbers of events in small registers. Commun. ACM 21, 10 (1978), 840\u2013842.","journal-title":"Commun. ACM"},{"issue":"2","key":"e_1_3_2_69_2","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1561\/0400000002","article-title":"Data streams: Algorithms and applications","volume":"1","author":"Muthukrishnan Shanmugavelayutham","year":"2005","unstructured":"Shanmugavelayutham Muthukrishnan et\u00a0al. 2005. Data streams: Algorithms and applications. Found. Trends Theoret. Comput. Sci. 1, 2 (2005), 117\u2013236.","journal-title":"Found. Trends Theoret. Comput. Sci."},{"issue":"4","key":"e_1_3_2_70_2","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF01305237","article-title":"Pseudorandom generators for space-bounded computation","volume":"12","author":"Nisan Noam","year":"1992","unstructured":"Noam Nisan. 1992. Pseudorandom generators for space-bounded computation. Combinatorica 12, 4 (1992), 449\u2013461.","journal-title":"Combinatorica"},{"key":"e_1_3_2_71_2","doi-asserted-by":"crossref","unstructured":"John P. Nolan. 2020. Univariate stable distributions. Springer Series in Operations Research and Financial Engineering 10 (2020) 978\u20133.","DOI":"10.1007\/978-3-030-52915-4"},{"key":"e_1_3_2_72_2","volume-title":"Random Sampling from Databases","author":"Olken Frank","year":"1993","unstructured":"Frank Olken. 1993. Random Sampling from Databases. Ph.D. Dissertation. University of California, Berkeley."},{"key":"e_1_3_2_73_2","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/978-3-642-24100-0_27","volume-title":"Proceedings of the International Symposium on Distributed Computing","author":"Tirthapura Srikanta","year":"2011","unstructured":"Srikanta Tirthapura and David P. Woodruff. 2011. Optimal random sampling from distributed streams revisited. In Proceedings of the International Symposium on Distributed Computing. Springer, 283\u2013297."},{"key":"e_1_3_2_74_2","doi-asserted-by":"crossref","first-page":"1082","DOI":"10.1007\/978-3-662-47672-7_88","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming","author":"Weinstein Omri","year":"2015","unstructured":"Omri Weinstein and David P. Woodruff. 2015. The simultaneous communication of disjointness with applications to data streams. In Proceedings of the International Colloquium on Automata, Languages, and Programming. Springer, 1082\u20131093."},{"key":"e_1_3_2_75_2","first-page":"167","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Woodruff David","year":"2004","unstructured":"David Woodruff. 2004. Optimal space lower bounds for all frequency moments. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 167\u2013175."},{"issue":"1","key":"e_1_3_2_76_2","first-page":"1","article-title":"Sketching as a tool for numerical linear algebra","volume":"10","author":"Woodruff David P.","year":"2014","unstructured":"David P. Woodruff et\u00a0al. 2014. Sketching as a tool for numerical linear algebra. Found. Trends Theoret. Comput. Sci. 10, 1\u20132 (2014), 1\u2013157.","journal-title":"Found. Trends Theoret. Comput. Sci."},{"key":"e_1_3_2_77_2","first-page":"941","volume-title":"Proceedings of the 44th Annual ACM Symposium on Theory of Computing","author":"Woodruff David P.","year":"2012","unstructured":"David P. Woodruff and Qin Zhang. 2012. Tight bounds for distributed functional monitoring. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing. ACM, 941\u2013960."},{"key":"e_1_3_2_78_2","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1145\/3196959.3196964","volume-title":"Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems","author":"Woodruff David P.","year":"2018","unstructured":"David P. Woodruff and Qin Zhang. 2018. Distributed statistical estimation of matrix products with applications. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 383\u2013394."},{"key":"e_1_3_2_79_2","first-page":"847","volume-title":"Proceedings of the IEEE 32nd International Conference on Data Engineering (ICDE)","author":"Woodruff David P.","year":"2016","unstructured":"David P. Woodruff and Peilin Zhong. 2016. Distributed low rank approximation of implicit functions of a matrix. In Proceedings of the IEEE 32nd International Conference on Data Engineering (ICDE). IEEE, 847\u2013858."},{"issue":"1","key":"e_1_3_2_80_2","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/s00453-011-9584-4","article-title":"Optimal tracking of distributed heavy hitters and quantiles","volume":"65","author":"Yi Ke","year":"2013","unstructured":"Ke Yi and Qin Zhang. 2013. Optimal tracking of distributed heavy hitters and quantiles. Algorithmica 65, 1 (2013), 206\u2013223.","journal-title":"Algorithmica"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3596494","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3596494","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:48:00Z","timestamp":1750178880000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3596494"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,24]]},"references-count":79,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7,31]]}},"alternative-id":["10.1145\/3596494"],"URL":"https:\/\/doi.org\/10.1145\/3596494","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,24]]},"assertion":[{"value":"2021-07-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-09","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}