{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:46:24Z","timestamp":1781077584435,"version":"3.54.1"},"reference-count":100,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["2335411"],"award-info":[{"award-number":["2335411"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>In this paper, we study streaming algorithms that minimize the number of changes made to their internal state (i.e., memory contents). While the design of streaming algorithms typically focuses on minimizing space and update time, these metrics fail to capture the asymmetric costs, inherent in modern hardware and database systems, of reading versus writing to memory. In fact, most streaming algorithms write to their memory on every update, which is undesirable when writing is significantly more expensive than reading. This raises the question of whether streaming algorithms with small space and number of memory writes are possible.<\/jats:p>\n          <jats:p>\n            We first demonstrate that, for the fundamental F\n            <jats:sub>p<\/jats:sub>\n            moment estimation problem with p \u2265 1, any streaming algorithm that achieves a constant factor approximation must make \u03a9(n\n            <jats:sup>1-1\/p<\/jats:sup>\n            ) internal state changes, regardless of how much space it uses. Perhaps surprisingly, we show that this lower bound can be matched by an algorithm which also has near-optimal space complexity. Specifically, we give a (1+\u03b5)-approximation algorithm for F\n            <jats:sub>p<\/jats:sub>\n            moment estimation that use a near-optimal ~O\n            <jats:sub>\u03b5<\/jats:sub>\n            (n\n            <jats:sup>1-1\/p<\/jats:sup>\n            ) number of state changes, while simultaneously achieving near-optimal space, i.e., for p\u2208[1,2), our algorithm uses poly(log n,1\/\u03b5) bits of space for, while for p&gt;2, the algorithm uses ~O\n            <jats:sub>\u03b5<\/jats:sub>\n            (n\n            <jats:sup>1-1\/p<\/jats:sup>\n            ) space. We similarly design streaming algorithms that are simultaneously near-optimal in both space complexity and the number of state changes for the heavy-hitters problem, sparse support recovery, and entropy estimation. Our results demonstrate that an optimal number of state changes can be achieved without sacrificing space complexity.\n          <\/jats:p>","DOI":"10.1145\/3651145","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-28","source":"Crossref","is-referenced-by-count":3,"title":["Streaming Algorithms with Few State Changes"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0332-6332","authenticated-orcid":false,"given":"Rajesh","family":"Jayaram","sequence":"first","affiliation":[{"name":"Google Research, New York City, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2158-1380","authenticated-orcid":false,"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Google Research, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8288-5698","authenticated-orcid":false,"given":"Samson","family":"Zhou","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University, College Station, TX, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"ICALP Proceedings, Part II. 328--338","author":"Ahn Kook Jin","year":"2009","unstructured":"Kook Jin Ahn and Sudipto Guha. 2009. Graph Sparsification in the Semi-streaming Model. In Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP Proceedings, Part II. 328--338."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3526228"},{"key":"e_1_2_1_3_1","volume-title":"Onyx: A Prototype Phase Change Memory Storage Array. In 3rd USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage1.","author":"Akel Ameen","year":"2011","unstructured":"Ameen Akel, Adrian M. Caulfield, Todor I. Mollov, Rajesh K. Gupta, and Steven Swanson. 2011. Onyx: A Prototype Phase Change Memory Storage Array. In 3rd USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage1."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1813"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.82"},{"key":"e_1_2_1_7_1","unstructured":"Apple. 2023. https:\/\/developer.apple.com\/documentation\/xcode\/reducing-disk-writes"},{"key":"e_1_2_1_8_1","volume-title":"International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures - ADMS. 23--32","author":"Athanassoulis Manos","unstructured":"Manos Athanassoulis, Bishwaranjan Bhattacharjee, Mustafa Canim, and Kenneth A. Ross. 2012. Path processing using Solid State Storage. In International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures - ADMS. 23--32."},{"key":"e_1_2_1_9_1","volume-title":"Woodruff","author":"Ba Khanh Do","year":"2010","unstructured":"Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff. 2010. Lower Bounds for Sparse Recovery. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 1190--1197."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Thirteenth ACM Symposium on Operating System Principles, SOSP. 198--212","author":"Baker Mary","unstructured":"Mary Baker, John H. Hartman, Michael D. Kupfer, Ken Shirriff, and John K. Ousterhout. 1991. Measurements of a Distributed File System. In Proceedings of the Thirteenth ACM Symposium on Operating System Principles, SOSP. 198--212."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921669"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8057216"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498334"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC. 716--729","author":"Blasiok Jaroslaw","unstructured":"Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang. 2017. Streaming symmetric norms via measure concentration. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC. 716--729."},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"Continuous Monitoring of l_p Norms in Data Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"32","author":"Blasiok Jaroslaw","year":"2017","unstructured":"Jaroslaw Blasiok, Jian Ding, and Jelani Nelson. 2017. Continuous Monitoring of l_p Norms in Data Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM. 32:1--32:13.","journal-title":"APPROX\/RANDOM."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755604"},{"key":"e_1_2_1_19_1","volume-title":"The Eleventh International Conference on Learning Representations, ICLR.","author":"Blocki Jeremiah","year":"2023","unstructured":"Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee, and Samson Zhou. 2023. Differentially Private L2-Heavy Hitters Model. In The Eleventh International Conference on Learning Representations, ICLR."},{"key":"e_1_2_1_20_1","volume-title":"MJRTY: A Fast Majority Vote Algorithm. In Automated Reasoning: Essays in Honor of Woody Bledsoe (Automated Reasoning Series). 105--118.","author":"Boyer Robert S.","year":"1991","unstructured":"Robert S. Boyer and J. Strother Moore. 1991. MJRTY: A Fast Majority Vote Algorithm. In Automated Reasoning: Essays in Honor of Woody Bledsoe (Automated Reasoning Series). 105--118."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS. 361--376","author":"Braverman Vladimir","unstructured":"Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David P. Woodruff. 2017. BPTree: An l2 Heavy Hitters Algorithm Using Constant Memory. In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS. 361--376."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC. 740--753","author":"Braverman Vladimir","unstructured":"Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, and David P. Woodruff. 2016. Beating CountSketch for heavy hitters in insertion streams. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC. 740--753."},{"key":"e_1_2_1_23_1","volume-title":"Near Optimal Linear Algebra in the Online and Sliding Window Models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS. 517--528","author":"Braverman Vladimir","year":"2020","unstructured":"Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. 2020. Near Optimal Linear Algebra in the Online and Sliding Window Models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS. 517--528."},{"key":"e_1_2_1_24_1","first-page":"1","article-title":"Streaming Coreset Constructions for M-Estimators. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"62","author":"Braverman Vladimir","year":"2019","unstructured":"Vladimir Braverman, Dan Feldman, Harry Lang, and Daniela Rus. 2019. Streaming Coreset Constructions for M-Estimators. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM. 62:1--62:15.","journal-title":"APPROX\/RANDOM."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3180808"},{"key":"e_1_2_1_26_1","volume-title":"Asian Conference on Machine Learning, ACML. 948--963","author":"Braverman Vladimir","year":"2021","unstructured":"Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou. 2021. Efficient Coreset Constructions via Sensitivity Sampling. In Asian Conference on Machine Learning, ACML. 948--963."},{"key":"e_1_2_1_27_1","first-page":"1","article-title":"Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"7","author":"Braverman Vladimir","year":"2018","unstructured":"Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, and Samson Zhou. 2018. Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM. 7:1--7:22.","journal-title":"APPROX\/RANDOM."},{"key":"e_1_2_1_28_1","volume-title":"Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPSl. 3544--3557","author":"Braverman Vladimir","year":"2021","unstructured":"Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. 2021. Adversarial Robustness of Streaming Algorithms through Importance Sampling. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPSl. 3544--3557."},{"key":"e_1_2_1_29_1","unstructured":"Vladimir Braverman Jonathan Katzman Charles Seidell and Gregory Vorsanger. 2014. An Optimal Algorithm for Large Frequency Moments Using O(n(1--2\/k)) Bits. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM. 531--544."},{"key":"e_1_2_1_30_1","first-page":"1","article-title":"Private Data Stream Analysis for Universal Symmetric Norm Estimation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"45","author":"Braverman Vladimir","year":"2023","unstructured":"Vladimir Braverman, Joel Manning, Zhiwei Steven Wu, and Samson Zhou. 2023. Private Data Stream Analysis for Universal Symmetric Norm Estimation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM. 45:1--45:24.","journal-title":"APPROX\/RANDOM."},{"key":"e_1_2_1_31_1","volume-title":"APPROX 2013, and 17th International Workshop, RANDOM. Proceedings. 42--57","author":"Braverman Vladimir","year":"2013","unstructured":"Vladimir Braverman and Rafail Ostrovsky. 2013. Approximating Large Frequency Moments with Pick-and-Drop Sampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM. Proceedings. 42--57."},{"key":"e_1_2_1_32_1","first-page":"1","article-title":"Revisiting Frequency Moment Estimation in Random Order Streams. In 45th International Colloquium on Automata, Languages, and Programming","volume":"25","author":"Braverman Vladimir","year":"2018","unstructured":"Vladimir Braverman, Emanuele Viola, David P. Woodruff, and Lin F. Yang. 2018. Revisiting Frequency Moment Estimation in Random Order Streams. In 45th International Colloquium on Automata, Languages, and Programming, ICALP. 25:1--25:14.","journal-title":"ICALP."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings. 528--539","author":"Braverman Vladimir","year":"2021","unstructured":"Vladimir Braverman, Viska Wei, and Samson Zhou. 2021. Symmetric Norm Estimation and Regression on Sliding Windows. In Computing and Combinatorics - 27th International Conference, COCOON, Proceedings. 528--539."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1244002.1244248"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278480.1278533"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00400-6"},{"key":"e_1_2_1_37_1","volume-title":"Rethinking Database Algorithms for Phase Change Memory. In Fifth Biennial Conference on Innovative Data Systems Research, CIDR. 21--31","author":"Chen Shimin","year":"2011","unstructured":"Shimin Chen, Phillip B. Gibbons, and Suman Nath. 2011. Rethinking Database Algorithms for Phase Change Memory. In Fifth Biennial Conference on Innovative Data Systems Research, CIDR. 21--31."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/UCC.2012.26"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1669112.1669157"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2020.v016a015"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00057"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 18th International Conference on Data Engineering. 605--614","author":"Cormode Graham","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. 605--614."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1687399.1687449"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391610"},{"key":"e_1_2_1_46_1","volume-title":"SEA. Proceedings. 162--173","author":"Eppstein David","year":"2014","unstructured":"David Eppstein, Michael T. Goodrich, Michael Mitzenmacher, and Pawel Pszona. 2014. Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One Basket. In Experimental Algorithms - 13th International Symposium, SEA. Proceedings. 162--173."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/633025.633056"},{"key":"e_1_2_1_48_1","volume-title":"Ullman","author":"Fang Min","year":"1998","unstructured":"Min Fang, Narayanan Shivakumar, Hector Garcia-Molina, Rajeev Motwani, and Jeffrey D. Ullman. 1998. Computing Iceberg Queries Efficiently. In VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases. 299--310."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361701"},{"key":"e_1_2_1_50_1","first-page":"1","article-title":"High Probability Frequency Moment Sketches. In 45th International Colloquium on Automata, Languages, and Programming","volume":"58","author":"Ganguly Sumit","year":"2018","unstructured":"Sumit Ganguly and David P. Woodruff. 2018. High Probability Frequency Moment Sketches. In 45th International Colloquium on Automata, Languages, and Programming, ICALP. 58:1--58:15.","journal-title":"ICALP."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1009718"},{"key":"e_1_2_1_52_1","volume-title":"26th International Symposium on Theoretical Aspects of Computer Science, STACS Proceedings. 505--516.","author":"Gronemeier Andr\u00e9","unstructured":"Andr\u00e9 Gronemeier. 2009. Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness. In 26th International Symposium on Theoretical Aspects of Computer Science, STACS Proceedings. 505--516."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.76"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007413"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465217"},{"key":"e_1_2_1_57_1","volume-title":"Woodruff","author":"Indyk Piotr","year":"2022","unstructured":"Piotr Indyk, Shyam Narayanan, and David P. Woodruff. 2022. Frequency Estimation with One-Sided Error. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA. 695--707."},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing. 202--208","author":"Indyk Piotr","unstructured":"Piotr Indyk and David P. Woodruff. 2005. Optimal approximations of the frequency moments of data streams. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing. 202--208."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02835833"},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 341--354","author":"Jayaram Rajesh","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--354."},{"key":"e_1_2_1_61_1","volume-title":"59th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 544--555","author":"Jayaram Rajesh","unstructured":"Rajesh Jayaram and David P. Woodruff. 2018. Perfect Lp Sampling in a Data Stream. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 544--555."},{"key":"e_1_2_1_62_1","first-page":"1","article-title":"Towards Optimal Moment Estimation in Streaming and Distributed Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"2019","author":"Jayaram Rajesh","year":"2019","unstructured":"Rajesh Jayaram and David P. Woodruff. 2019. Towards Optimal Moment Estimation in Streaming and Distributed Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2019. 29:1--29:21.","journal-title":"APPROX\/RANDOM"},{"key":"e_1_2_1_63_1","volume-title":"Truly Perfect Samplers for Data Streams and Sliding Windows. In PODS '22: International Conference on Management of Data","author":"Jayaram Rajesh","year":"2022","unstructured":"Rajesh Jayaram, David P. Woodruff, and Samson Zhou. 2022. Truly Perfect Samplers for Data Streams and Sliding Windows. In PODS '22: International Conference on Management of Data, Philadelphia. 29--40."},{"key":"e_1_2_1_64_1","volume-title":"12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM. Proceedings.","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 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM. Proceedings."},{"key":"e_1_2_1_65_1","volume-title":"The Data Stream Space Complexity of Cascaded Norms. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS. 765--774","author":"Jayram T. S.","unstructured":"T. S. Jayram and David P. Woodruff. 2009. The Data Stream Space Complexity of Cascaded Norms. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS. 765--774."},{"key":"e_1_2_1_66_1","volume-title":"Learning-Augmented Data Stream Algorithms. In 8th International Conference on Learning Representations, ICLR.","author":"Jiang Tanqiu","unstructured":"Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P. Woodruff. 2020. Learning-Augmented Data Stream Algorithms. In 8th International Conference on Learning Representations, ICLR."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_2_1_68_1","volume-title":"Woodruff","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 Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 1161--1178."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2668128"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.16"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588673"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555754.1555758"},{"key":"e_1_2_1_73_1","volume-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS.","author":"Levin Roie","unstructured":"Roie Levin, Anish Prasad Sevekari, and David P. Woodruff. 2018. Robust Subspace Approximation in a Stream. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347084"},{"key":"e_1_2_1_75_1","first-page":"1","article-title":"On Low-Risk Heavy Hitters and Sparse Recovery Schemes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"19","author":"Li Yi","year":"2018","unstructured":"Yi Li, Vasileios Nakos, and David P. Woodruff. 2018. On Low-Risk Heavy Hitters and Sparse Recovery Schemes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM. 19:1--19:13.","journal-title":"APPROX\/RANDOM."},{"key":"e_1_2_1_76_1","volume-title":"Woodruff","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 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM. Proceedings. 623--638."},{"key":"e_1_2_1_77_1","unstructured":"Sepideh Mahabadi David P. Woodruff and Samson Zhou. 2022. Adaptive Sketches for Robust Regression with Importance Sampling. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques APPROX\/RANDOM) Amit Chakrabarti and Chaitanya Swamy (Eds.). 31:1--31:21."},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367508"},{"key":"e_1_2_1_79_1","volume-title":"Umesh Chand, and Tseung-Yuen Tseng.","author":"Meena Jagan Singh","year":"2014","unstructured":"Jagan Singh Meena, Simon Min Sze, Umesh Chand, and Tseung-Yuen Tseng. 2014. Overview of emerging nonvolatile memory technologies. Nanoscale research letters 9 (2014), 1--33."},{"key":"e_1_2_1_80_1","volume-title":"10th International Conference, Proceedings. 398--412","author":"Metwally Ahmed","year":"2005","unstructured":"Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. 2005. Efficient Computation of Frequent and Top-k Elements in Data Streams. In Database Theory - ICDT 2005, 10th International Conference, Proceedings. 398--412."},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359627"},{"key":"e_1_2_1_83_1","doi-asserted-by":"crossref","unstructured":"Shanmugavelayutham Muthukrishnan et al . 2005. Data streams: Algorithms and applications. Foundations and Trends\u00ae in Theoretical Computer Science 1 2 (2005) 117--236.","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/1416944.1416949"},{"key":"e_1_2_1_85_1","volume-title":"Optimal Bounds for Approximate Counting. In PODS '22: International Conference on Management of Data. ACM, 119--127","author":"Nelson Jelani","year":"2022","unstructured":"Jelani Nelson and Huacheng Yu. 2022. Optimal Bounds for Approximate Counting. In PODS '22: International Conference on Management of Data. ACM, 119--127."},{"key":"e_1_2_1_86_1","volume-title":"Stable distributions: models for heavy-tailed data","author":"Nolan John","unstructured":"John Nolan. 2003. Stable distributions: models for heavy-tailed data. Birkhauser New York."},{"key":"e_1_2_1_87_1","volume-title":"Phase Change Memory: From Devices to Systems","author":"Qureshi Moinuddin K.","unstructured":"Moinuddin K. Qureshi, Sudhanva Gurumurthi, and Bipin Rajendran. 2011. Phase Change Memory: From Devices to Systems. Morgan & Claypool Publishers."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/1966445.1966461"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.5555\/982792.982884"},{"key":"e_1_2_1_90_1","volume-title":"ADBIS. Proceedings. 399--412","author":"Viglas Stratis","year":"2012","unstructured":"Stratis Viglas. 2012. Adapting the B -tree for Asymmetric I\/O. In Advances in Databases and Information Systems - 16th East European Conference, ADBIS. Proceedings. 399--412."},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732277"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.5555\/982792.982817"},{"key":"e_1_2_1_93_1","volume-title":"Proceedings of the 44th Symposium on Theory of Computing Conference, STOC. 941--960","author":"David","unstructured":"David P. Woodruff and Qin Zhang. 2012. Tight bounds for distributed functional monitoring. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC. 941--960."},{"key":"e_1_2_1_94_1","first-page":"1","article-title":"Separations for Estimating Large Frequency Moments on Data Streams. In 48th International Colloquium on Automata, Languages, and Programming","volume":"112","author":"Woodruff David P.","year":"2021","unstructured":"David P. Woodruff and Samson Zhou. 2021. Separations for Estimating Large Frequency Moments on Data Streams. In 48th International Colloquium on Automata, Languages, and Programming, ICALP. 112:1--112:21.","journal-title":"ICALP."},{"key":"e_1_2_1_95_1","volume-title":"62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS. 1183--1196","author":"David","unstructured":"David P. Woodruff and Samson Zhou. 2021. Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS. 1183--1196."},{"key":"e_1_2_1_96_1","doi-asserted-by":"crossref","unstructured":"Cong Xu Xiangyu Dong Norman P. Jouppi and Yuan Xie. 2011. Design implications of memristor-based RRAM cross-point structures. In Design Automation and Test in Europe DATE. 734--739.","DOI":"10.1109\/DATE.2011.5763125"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCAS.2007.377981"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555754.1555759"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095810.1095828"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1989-15794-7"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651145","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651145","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:33Z","timestamp":1755898773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651145"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":100,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651145"],"URL":"https:\/\/doi.org\/10.1145\/3651145","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}