{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,6]],"date-time":"2022-04-06T01:50:56Z","timestamp":1649209856657},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0514870CCF-0830626"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2012,1]]},"abstract":"We consider the read\/write streams model, an extension of the standard data stream model in which an algorithm can create and manipulate multiple read\/write streams in addition to its input data stream. Like the data stream model, the most important parameter for this model is the amount of internal memory used by such an algorithm. The other key parameters are the number of streams the algorithm uses and the number of passes it makes on these streams. We consider how the addition of multiple streams impacts the ability of algorithms to approximate the frequency moments of the input stream.<\/jats:p>\n \n We show that any randomized read\/write stream algorithm with a fixed number of streams and a sublogarithmic number of passes that produces a constant factor approximation of the\n k<\/jats:italic>\n -th frequency moment\n F<\/jats:italic>\n k<\/jats:sub>\n of an input sequence of length of at most\n N<\/jats:italic>\n from {1,...,\n N<\/jats:italic>\n } requires space\n \u03a9<\/jats:italic>\n (\n N<\/jats:italic>\n 1\u22124\/k\u2212\u03b4<\/jats:sup>\n ) for any\n \u03b4<\/jats:italic>\n \u2009>\u20090. For comparison, it is known that with a single read-only one-pass data stream there is a randomized constant-factor approximation for\n F<\/jats:italic>\n k<\/jats:sub>\n using\n \u00d5<\/jats:italic>\n (\n N<\/jats:italic>\n 1\u22122\/k<\/jats:sup>\n ) space, and that by sorting, which can be done deterministically in\n O<\/jats:italic>\n (log\n N<\/jats:italic>\n ) passes using 3 read\/write streams,\n F<\/jats:italic>\n k<\/jats:sub>\n can be computed exactly. Therefore, although the ability to manipulate multiple read\/write streams can add substantial power to the data stream model, with a sublogarithmic number of passes this does not significantly improve the ability to approximate higher frequency moments efficiently. We obtain our results by showing a new connection between the read\/write streams model and the multiparty number-in-hand communication model.\n <\/jats:p>","DOI":"10.1145\/2077336.2077339","type":"journal-article","created":{"date-parts":[[2012,2,7]],"date-time":"2012-02-07T15:39:28Z","timestamp":1328629168000},"page":"1-22","source":"Crossref","is-referenced-by-count":1,"title":["The Value of Multiple Read\/Write Streams for Approximating Frequency Moments"],"prefix":"10.1145","volume":"3","author":[{"given":"Paul","family":"Beame","sequence":"first","affiliation":[{"name":"University of Washington"}]},{"given":"Trinh","family":"Huynh","sequence":"additional","affiliation":[{"name":"University of Washington"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_4_1","unstructured":"Beame P. Blais E. and Huynh-Ngoc D.-T. 2009. Longest common subsequences in sets of permutations. Tech. rep. arXiv:R0904.1615v1 {math.CO}. Beame P. Blais E. and Huynh-Ngoc D.-T. 2009. Longest common subsequences in sets of permutations. Tech. rep. arXiv:R0904.1615v1 {math.CO}."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.52"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250891"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109634"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 18th Annual IEEE Conference on Computational Complexity. 107--117","author":"Chakrabarti A."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993644"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065197"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142387"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516514"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 26th Annual Symposium on Theoretical Aspects of Computer Science. 505--516","author":"Gronemeier A.","year":"2009"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 44th Annual Symposium on Foundations of Computer Science. IEEE, 283--292","author":"Indyk P."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060621"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_42"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509963"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Steele J. M. 1995. Variations on the monotone subsequence problem of Erd\u00f6s and Szekeres. In Discrete Probability and Algorithms Aldous Diaconis and Steele Eds. Springer 111--132. Steele J. M. 1995. Variations on the monotone subsequence problem of Erd\u00f6s and Szekeres. In Discrete Probability and Algorithms Aldous Diaconis and Steele Eds. Springer 111--132.","DOI":"10.1007\/978-1-4612-0801-3_9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Steele J. M. 1997. Probability Theory and Combinatorial Optimization. SIAM Philadelphia PA. Steele J. M. 1997. Probability Theory and Combinatorial Optimization . SIAM Philadelphia PA.","DOI":"10.1137\/1.9781611970029"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. 167--175","author":"Woodruff D.","year":"2004"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2077336.2077339","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,21]],"date-time":"2021-02-21T16:56:24Z","timestamp":1613926584000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2077336.2077339"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2077336.2077339"],"URL":"http:\/\/dx.doi.org\/10.1145\/2077336.2077339","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":["Computational Theory and Mathematics","Theoretical Computer Science"],"published":{"date-parts":[[2012,1]]}}}