{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:49:31Z","timestamp":1781077771623,"version":"3.54.1"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,5,13]],"date-time":"2014-05-13T00:00:00Z","timestamp":1399939200000},"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":["SIGMOD Rec."],"published-print":{"date-parts":[[2014,5,13]]},"abstract":"<jats:p>Over the last decade, there has been considerable interest in designing algorithms for processing massive graphs in the data stream model. The original motivation was two-fold: a) in many applications, the dynamic graphs that arise are too large to be stored in the main memory of a single machine and b) considering graph problems yields new insights into the complexity of stream computation. However, the techniques developed in this area are now finding applications in other areas including data structures for dynamic graphs, approximation algorithms, and distributed and parallel computation. We survey the state-of-the-art results; identify general techniques; and highlight some simple algorithms that illustrate basic ideas.<\/jats:p>","DOI":"10.1145\/2627692.2627694","type":"journal-article","created":{"date-parts":[[2014,5,27]],"date-time":"2014-05-27T12:56:59Z","timestamp":1401195419000},"page":"9-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":247,"title":["Graph stream algorithms"],"prefix":"10.1145","volume":"43","author":[{"given":"Andrew","family":"McGregor","sequence":"first","affiliation":[{"name":"University of Massachusetts"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,5,13]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"University of Pennsylvania","author":"Ahn K. J.","year":"2013"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_27"},{"key":"e_1_2_1_3_1","unstructured":"K. J. Ahn and S. Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. CoRR abs\/1307.4359 2013.  K. J. Ahn and S. Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. CoRR abs\/1307.4359 2013."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.006"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095156"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_1"},{"key":"e_1_2_1_8_1","unstructured":"M. Badoiu A. Sidiropoulos and V. Vaikuntanathan. Computing s-t min-cuts in a semi-streaming model. Manuscript.  M. Badoiu A. Sidiropoulos and V. Vaikuntanathan. Computing s-t min-cuts in a semi-streaming model. Manuscript."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_2_1_10_1","first-page":"623","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"Bar-Yossef Z.","year":"2002"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.11.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772873"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839494"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_2_1_15_1","volume-title":"Academic Press","author":"Bollob\u00e1s B.","year":"1978"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.63"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_21"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374470"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"A. Chakrabarti and S. Kale. Submodular maximization meets streaming: Matchings matroids and more. CoRR arXiv:1309.2038 2013.  A. Chakrabarti and S. Kale. Submodular maximization meets streaming: Matchings matroids and more. CoRR arXiv:1309.2038 2013.","DOI":"10.1007\/978-3-319-07557-0_18"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065201"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_29"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921666"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0147-2"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/100801901"},{"key":"e_1_2_1_26_1","first-page":"389","volume-title":"STACS","author":"Epstein L.","year":"2013"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993647"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095157"},{"key":"e_1_2_1_31_1","unstructured":"A. Goel M. Kapralov and I. Post. Single pass sparsification in the streaming model with edge deletions. CoRR abs\/1203.4900 2012.  A. Goel M. Kapralov and I. Post. Single pass sparsification in the streaming model with edge deletions. CoRR abs\/1203.4900 2012."},{"key":"e_1_2_1_32_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1007\/978-3-642-22670-0_32","volume-title":"Studies in Complexity and Cryptography","author":"Goldreich O.","year":"2011"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.37"},{"key":"e_1_2_1_34_1","first-page":"641","volume-title":"Languages and Programming","author":"Halld\u00f3rsson B. V.","year":"2010"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_38"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"M. R. Henzinger P. Raghavan and S. Rajagopalan. Computing on data streams. External memory algorithms pages 107--118 1999.   M. R. Henzinger P. Raghavan and S. Rajagopalan. Computing on data streams. External memory algorithms pages 107--118 1999.","DOI":"10.1090\/dimacs\/050\/05"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487678"},{"key":"e_1_2_1_38_1","unstructured":"M. Jha C. Seshadhri and A. Pinar. When a graph is not so simple: Counting triangles in multigraph streams. CoRR arXiv:1310.7665 2013.  M. Jha C. Seshadhri and A. Pinar. When a graph is not so simple: Counting triangles in multigraph streams. CoRR arXiv:1310.7665 2013."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2958119.2958158"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_53"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627938"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.55"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627898"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195422"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9396-1"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_20"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_54"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433480"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2040572.2040646"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_15"},{"key":"e_1_2_1_52_1","volume-title":"Now Publishers","author":"Muthukrishnan S.","year":"2006"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.12.007"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556569"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095158"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970397"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.046"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_2_1_60_1","volume-title":"SIAM","author":"Tarjan R.","year":"1983"},{"key":"e_1_2_1_61_1","first-page":"379","volume-title":"Languages and Programming","author":"Varadaraja A. B.","year":"2011"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9438-5"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2627692.2627694","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2627692.2627694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:36Z","timestamp":1750230096000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2627692.2627694"}},"subtitle":["a survey"],"short-title":[],"issued":{"date-parts":[[2014,5,13]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,5,13]]}},"alternative-id":["10.1145\/2627692.2627694"],"URL":"https:\/\/doi.org\/10.1145\/2627692.2627694","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2014,5,13]]},"assertion":[{"value":"2014-05-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}