{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T13:10:30Z","timestamp":1737378630379,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540735441"},{"type":"electronic","value":"9783540735458"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73545-8_34","type":"book-chapter","created":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T13:44:11Z","timestamp":1187358251000},"page":"338-348","source":"Crossref","is-referenced-by-count":0,"title":["Streaming Algorithms Measured in Terms of the Computed Quantity"],"prefix":"10.1007","author":[{"given":"Shengyu","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"34_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. Journal of Computer and System Sciences\u00a058(1), 137\u2013147 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"34_CR2","first-page":"623","volume-title":"SODA","author":"Z. Bar-Yossef","year":"2002","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: SODA. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 623\u2013632. ACM Press, New York (2002)"},{"key":"34_CR3","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1109\/SFCS.2002.1181944","volume-title":"Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science","author":"Z. Bar-Yossef","year":"2002","unstructured":"Bar-Yossef, Z., Jayram, T., Kumar, R., Sivakumar, D.: Information statistics approach to data stream and communication complexity. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 209\u2013218. IEEE Computer Society Press, Los Alamitos (2002)"},{"key":"34_CR4","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1016\/S0304-3975(02)00569-8","volume":"299","author":"A. Buchsbaum","year":"2003","unstructured":"Buchsbaum, A., Giancarlo, R., Westbrook, J.: On finding common neighborhoods in massive graphs. Theoretical Computer Science\u00a0299, 707\u2013718 (2003)","journal-title":"Theoretical Computer Science"},{"key":"34_CR5","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1145\/1142351.1142388","volume-title":"Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems","author":"L. Buriol","year":"2006","unstructured":"Buriol, L., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., Sohler, C.: Counting Triangles in Data Streams. In: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 253\u2013262. ACM Press, New York (2006)"},{"key":"34_CR6","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1109\/CCC.2003.1214414","volume-title":"Proceedings of the 18th IEEE Conference on Computational Complexity","author":"A. Chakrabarti","year":"2003","unstructured":"Chakrabarti, A., Khot, S., Sun, X.: Near-optimal lower bounds on the multi-party communication coplexity of set disjointness. In: Proceedings of the 18th IEEE Conference on Computational Complexity, pp. 107\u2013117. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"34_CR7","first-page":"151","volume-title":"SODA","author":"D. Coppersmith","year":"2004","unstructured":"Coppersmith, D., Kumar, R.: An improved data stream algorithm for frequency moments. In: SODA. Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, pp. 151\u2013156. ACM Press, New York (2004)"},{"key":"34_CR8","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1103\/PhysRevLett.94.160202","volume":"94","author":"I. Derenyi","year":"2005","unstructured":"Derenyi, I., Palla, G., Vicsek, T.: Clique percolation in random networks. Physical Review Letters\u00a094, 160\u2013202 (2005)","journal-title":"Physical Review Letters"},{"key":"34_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1007\/978-3-540-27836-8_46","volume-title":"Automata, Languages and Programming","author":"J. Feigenbaum","year":"2004","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 531\u2013543. Springer, Heidelberg (2004)"},{"key":"34_CR10","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph Distances in the Streaming Model: The Value of Space. In: Proceedings of the 16th Symposium on Discrete Algorithms (SODA), pp. 745\u2013754 (2005)"},{"key":"34_CR11","doi-asserted-by":"crossref","unstructured":"Feigenbaum, J., Kannan, S., Strauss, M., Viswanathan, M.: An approximate L1 difference algorithm for massive data streams. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pp. 501\u2013511 (1999)","DOI":"10.1109\/SFFCS.1999.814623"},{"key":"34_CR12","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1006\/jcta.1996.0067","volume":"75","author":"Z. Furedi","year":"1996","unstructured":"Furedi, Z.: New asymptotics for bipartite Turan numbers. Journal of Combinatorial Theory, Series A\u00a075, 141\u2013144 (1996)","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Ghodsi, M.: New Streaming Algorithms for Counting Triangles in Graphs. In: Proceedings of the Eleventh International Computing and Combinatorics Conference, pp. 710\u2013716 (2005)","DOI":"10.1007\/11533719_72"},{"key":"34_CR14","first-page":"202","volume-title":"Proceedings of the 37th 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: Proceedings of the 37th ACM Symposium on Theory of Computing, pp. 202\u2013208. ACM Press, New York (2005)"},{"key":"34_CR15","doi-asserted-by":"crossref","first-page":"50","DOI":"10.4064\/cm-3-1-50-57","volume":"3","author":"T. Kovari","year":"1954","unstructured":"Kovari, T., Sos, V.T., Turan, P.: On a problem of K. Zarankiewicz. Colloq. Math\u00a03, 50\u201357 (1954)","journal-title":"Colloq. Math"},{"issue":"2","key":"34_CR16","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. Roundations and Trends in Theoretical Computer Science\u00a01(2), 117\u2013236 (2005)","journal-title":"Roundations and Trends in Theoretical Computer Science"},{"key":"34_CR17","first-page":"360","volume-title":"Proceedings on 34th Annual ACM Symposium on Theory of Computing","author":"M. Saks","year":"2002","unstructured":"Saks, M., Sun, X.: Space lower bounds for distance approximation in the data stream model. In: Proceedings on 34th Annual ACM Symposium on Theory of Computing, pp. 360\u2013369. ACM Press, New York (2002)"},{"issue":"1","key":"34_CR18","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.physa.2006.11.072","volume":"378","author":"X. Shi","year":"2007","unstructured":"Shi, X., Adamic, L., Strauss, M.: Networks of strong ties. Physica A\u00a0378(1), 33\u201347 (2007)","journal-title":"Physica A"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73545-8_34.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T12:32:35Z","timestamp":1737376355000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73545-8_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540735441","9783540735458"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73545-8_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}