{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T21:31:39Z","timestamp":1767648699600},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_21","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T13:20:16Z","timestamp":1372771216000},"page":"244-254","source":"Crossref","is-referenced-by-count":19,"title":["How Hard Is Counting Triangles in the Streaming Model?"],"prefix":"10.1007","author":[{"given":"Vladimir","family":"Braverman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Vilenchik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. In: Proceedings of the 28th STOC, pp. 20\u201329 (1996)","DOI":"10.1145\/237814.237823"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"M. Alon","year":"1997","unstructured":"Alon, M., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica\u00a017, 209\u2013223 (1997)","journal-title":"Algorithmica"},{"key":"21_CR3","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proceedings of the 13th SODA, pp. 623\u2013632 (2002)"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Becchetti, L., Boldi, P., Castillo, C., Gionis, A.: Efficient semi-streaming algorithms for local triangle counting in massive graphs. In: Proceeding of the 14th ACM International Conference on Knowledge Discovery and Data Mining, pp. 16\u201324 (2008)","DOI":"10.1145\/1401890.1401898"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"Buriol, L., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., Sohler, C.: Counting triangles in data streams. In: Proceedings of the Twenty-Fifth ACM Symposium on Principles of database Systems, pp. 253\u2013262 (2006)","DOI":"10.1145\/1142351.1142388"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Cormode, G., Ranganath, K., McGregor, A.: Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. In: Proceedings of the 51st FOCS, pp. 387\u2013396 (2010)","DOI":"10.1109\/FOCS.2010.44"},{"key":"21_CR7","doi-asserted-by":"publisher","first-page":"5825","DOI":"10.1073\/pnas.032093399","volume":"99","author":"J. Eckmann","year":"2002","unstructured":"Eckmann, J., Moses, E.: Curvature of co-links uncovers hidden thematic layers in the world wide web. PNAS\u00a099, 5825\u20135829 (2002)","journal-title":"PNAS"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1080\/01621459.1986.10478342","volume":"81","author":"O. Frank","year":"1986","unstructured":"Frank, O., Strauss, D.: Markov graphs. Journal of the American Statistical Association\u00a081, 832\u2013842 (1986)","journal-title":"Journal of the American Statistical Association"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Janson, S., Luczak, T., and Ruci\u0144ski, A.: Random Graphs. Wiley (2000)","DOI":"10.1002\/9781118032718"},{"key":"21_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1007\/11533719_72","volume-title":"Computing and Combinatorics","author":"H. Jowhari","year":"2005","unstructured":"Jowhari, H., Ghodsi, M.: New streaming algorithms for counting triangles in graphs. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 710\u2013716. Springer, Heidelberg (2005)"},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1080\/15427951.2012.625260","volume":"8","author":"M. Kolountzakis","year":"2012","unstructured":"Kolountzakis, M., Miller, G., Peng, R., Tsourakakis, C.: Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning. Internet Mathematics\u00a08, 161\u2013185 (2012)","journal-title":"Internet Mathematics"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Backstrom, L., Kumar, R., Tomkins, A.: Microscopic evolution of social networks. In: Proceeding of the 14th ACM International Conference on Knowledge Discovery and Data Mining, pp. 462\u2013470 (2008)","DOI":"10.1145\/1401890.1401948"},{"key":"21_CR13","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1214\/08-EJS350","volume":"3","author":"A. Rinaldo","year":"2009","unstructured":"Rinaldo, A., Fienberg, S., Zhou, Y.: On the geometry of discrete exponential families with application to exponential random graph models. Electronic Journal of Statistics\u00a03, 446\u2013484 (2009)","journal-title":"Electronic Journal of Statistics"},{"key":"21_CR14","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s13278-010-0001-9","volume":"1","author":"C. Tsourakakis","year":"2011","unstructured":"Tsourakakis, C., Drineas, P., Michelakis, E., Koutis, I., Faloutsos, C.: Spectral counting of triangles via element-wise sparsification and triangle-based link recommendation. Social Network Analysis and Mining\u00a01, 75\u201381 (2011)","journal-title":"Social Network Analysis and Mining"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C., Kang, U., Miller, G., Faloutsos, C.: DOULION: counting triangles in massive graphs with a coin. In: Proceedings of the 15th ACM International Conference on Knowledge Discovery and Data Mining, pp. 837\u2013846 (2009)","DOI":"10.1145\/1557019.1557111"},{"key":"21_CR16","unstructured":"Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications. Cambridge University Press (2004)"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Vassilevska-Williams, V.: Multiplying matrices faster than Coppersmith-Winograd. In: Proceedings of the 44th STOC, pp. 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T05:30:10Z","timestamp":1557898210000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}