{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T03:06:02Z","timestamp":1787022362162,"version":"build-2736575974"},"reference-count":7,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,8]]},"abstract":"<jats:p>Massive graphs arise in any application where there is data about both basic entities and the relationships between these entities, e.g., web-pages and hyperlinks; neurons and synapses; papers and citations; IP addresses and network flows; people and their friendships. Graphs have also become the de facto standard for representing many types of highly structured data. However, the sheer size of many of these graphs renders classical algorithms inapplicable when it comes to analyzing such graphs. In addition, these existing algorithms are typically ill-suited to processing distributed or stream data.<\/jats:p>\n                  <jats:p>Various platforms have been developed for processing large data sets. At the same time, there is the need to develop new algorithmic ideas and paradigms. In the case of graph processing, a lot of recent work has focused on understanding the important algorithmic issues. An central aspect of this is the question of how to construct and leverage small-space synopses in graph processing. The goal of this tutorial is to survey recent work on this question and highlight interesting directions for future research.<\/jats:p>","DOI":"10.14778\/2367502.2367570","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T08:17:57Z","timestamp":1403597877000},"page":"2030-2031","source":"Crossref","is-referenced-by-count":29,"title":["Graph synopses, sketches, and streams"],"prefix":"10.14778","volume":"5","author":[{"given":"Sudipto","family":"Guha","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"McGregor","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, Amherst, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms","author":"Ahn K. J.","year":"2012","unstructured":"K. J. Ahn , S. Guha , and A. McGregor . Analyzing graph structure via linear measurements . In ACM-SIAM Symposium on Discrete Algorithms , 2012 . K. J. Ahn, S. Guha, and A. McGregor. Analyzing graph structure via linear measurements. In ACM-SIAM Symposium on Discrete Algorithms, 2012."},{"key":"e_1_2_1_2_1","volume-title":"ACM Symposium on Principles of Database Systems","author":"Ahn K. J.","year":"2012","unstructured":"K. J. Ahn , S. Guha , and A. McGregor . Graph sketching: Sparsification, spanners and subgraphs . In ACM Symposium on Principles of Database Systems , 2012 . 10.1145\/2213556.2213560 K. J. Ahn, S. Guha, and A. McGregor. Graph sketching: Sparsification, spanners and subgraphs. In ACM Symposium on Principles of Database Systems, 2012. 10.1145\/2213556.2213560"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_2_1_4_1","unstructured":"Giraph. http:\/\/incubator.apache.org\/giraph\/.  Giraph. http:\/\/incubator.apache.org\/giraph\/."},{"key":"e_1_2_1_5_1","volume-title":"Conference on Uncertainty in Artificial Intelligence (UAI)","author":"Low Y.","year":"2010","unstructured":"Y. Low , J. Gonzalez , A. Kyrola , D. Bickson , C. Guestrin , and J. M. Hellerstein . GraphLab: A new parallel framework for machine learning . In Conference on Uncertainty in Artificial Intelligence (UAI) , Catalina Island, California , July 2010 . Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. GraphLab: A new parallel framework for machine learning. In Conference on Uncertainty in Artificial Intelligence (UAI), Catalina Island, California, July 2010."},{"key":"e_1_2_1_6_1","first-page":"135","volume-title":"SIGMOD Conference","author":"Malewicz G.","year":"2010","unstructured":"G. Malewicz , M. H. Austern , A. J. C. Bik , J. C. Dehnert , I. Horn , N. Leiser , and G. Czajkowski . Pregel: a system for large-scale graph processing . In SIGMOD Conference , pages 135 -- 146 , 2010 . 10.1145\/1807167.1807184 G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD Conference, pages 135--146, 2010. 10.1145\/1807167.1807184"},{"key":"e_1_2_1_7_1","volume-title":"Data Streams: Algorithms and Applications","author":"Muthukrishnan S.","year":"2006","unstructured":"S. Muthukrishnan . Data Streams: Algorithms and Applications . Now Publishers , 2006 . S. Muthukrishnan. Data Streams: Algorithms and Applications. Now Publishers, 2006."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2367502.2367570","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T05:47:57Z","timestamp":1672206477000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2367502.2367570"}},"subtitle":["a survey"],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":7,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.14778\/2367502.2367570"],"URL":"https:\/\/doi.org\/10.14778\/2367502.2367570","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,8]]}}}