{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:52:35Z","timestamp":1773481955851,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":78,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T00:00:00Z","timestamp":1654819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF- 2118832, CCF-2106827, CSR-1763680, CCF-1716252, CNS-1938709, CSR 1938180, CCF 2106999, and CCF 2118620"],"award-info":[{"award-number":["CCF- 2118832, CCF-2106827, CSR-1763680, CCF-1716252, CNS-1938709, CSR 1938180, CCF 2106999, and CCF 2118620"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,10]]},"DOI":"10.1145\/3514221.3526146","type":"proceedings-article","created":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T02:33:49Z","timestamp":1655001229000},"page":"325-339","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams"],"prefix":"10.1145","author":[{"given":"David","family":"Tench","sequence":"first","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}]},{"given":"Evan","family":"West","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}]},{"given":"Victor","family":"Zhang","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}]},{"given":"Michael A.","family":"Bender","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}]},{"given":"Abiyaz","family":"Chowdhury","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}]},{"given":"J. Ahmed","family":"Dellas","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}]},{"given":"Martin","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, NJ, USA"}]},{"given":"Tyler","family":"Seip","sequence":"additional","affiliation":[{"name":"MongoDB, New York, NY, USA"}]},{"given":"Kenny","family":"Zhang","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,11]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0088-5"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.40"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2018.2858250"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1242\/jcs.02714"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPAS.2018.8708900"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3184470.3184473"},{"key":"e_1_3_2_2_8_1","first-page":"45","volume-title":"Introducing the Graph 500","author":"Ang J.","year":"2010","unstructured":"J. Ang, B. W. Barrett, K. B. Wheeler, and R. C. Murphy. Introducing the Graph 500. In Cray User Group (CUG), volume 19, pages 45--74, 2010."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60220-8_74"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150462"},{"key":"e_1_3_2_2_11_1","volume-title":"Web Science (WebSci)","author":"Bordino I.","year":"2009","unstructured":"I. Bordino and D. Donato. Dynamic characterization of a large web graph. In Web Science (WebSci), 2009."},{"key":"e_1_3_2_2_12_1","first-page":"1","volume-title":"19th International Symposium on Experimental Algorithms (SEA)","author":"Brodal G. S.","year":"2021","unstructured":"G. S. Brodal, R. Fagerberg, D. Hammer, U. Meyer, M. Penschuck, and H. Tran. An experimental study of external memory algorithms for connected components. In 19th International Symposium on Experimental Algorithms (SEA), pages 23:1--23:23, 2021."},{"key":"e_1_3_2_2_13_1","first-page":"280","volume-title":"European Parallel Virtual Machine\/Message Passing Interface Users' Group Meeting (EuroMPI)","author":"Buvs L.","year":"2001","unstructured":"L. Buvs and P. Tvrdik. A parallel algorithm for connected components on distributed memory machines. In European Parallel Virtual Machine\/Message Passing Interface Users' Group Meeting (EuroMPI), pages 280--287, 2001."},{"key":"e_1_3_2_2_14_1","first-page":"1","volume-title":"Hornet: An efficient data structure for dynamic sparse graphs and matrices on GPUs. In 2018 IEEE High Performance extreme Computing Conference (HPEC)","author":"Busato F.","year":"2018","unstructured":"F. Busato, O. Green, N. Bombieri, and D. A. Bader. Hornet: An efficient data structure for dynamic sparse graphs and matrices on GPUs. In 2018 IEEE High Performance extreme Computing Conference (HPEC), pages 1--7, 2018."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113362"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168846"},{"key":"e_1_3_2_2_17_1","first-page":"139","volume-title":"Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chiang Y.-J.","year":"1995","unstructured":"Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. External-memory graph algorithms. In Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 139--149, 1995."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_3_2_2_19_1","volume-title":"xxhash-extremely fast non-cryptographic hash algorithm. https:\/\/github. com\/Cyan4973\/xxHash","author":"Collet Y.","year":"2016","unstructured":"Y. Collet. xxhash-extremely fast non-cryptographic hash algorithm. https:\/\/github. com\/Cyan4973\/xxHash, 2016."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-013-7131-9"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314598"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2012.6408680"},{"key":"e_1_3_2_2_23_1","first-page":"226","volume-title":"ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)","author":"Ester M.","year":"1996","unstructured":"M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 226--231, 1996."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994538"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00013"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/181014.181021"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745763"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487581"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.10.013"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2017.04.018"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISDA.2010.5687244"},{"key":"e_1_3_2_2_33_1","first-page":"309","volume-title":"12th USENIX Symposium on Networked Systems Design and Implementation (NSDI)","author":"Iyer A.","year":"2015","unstructured":"A. Iyer, L. E. Li, and I. Stoica. CellIQ: Real-time cellular network analytics at scale. In 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI), pages 309--322, 2015."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960419"},{"key":"e_1_3_2_2_35_1","volume-title":"Random walk with restart on large graphs using block elimination. ACM Transactions on Database Systems (TODS), 41(2):1--43","author":"Jung J.","year":"2016","unstructured":"J. Jung, K. Shin, L. Sael, and U. Kang. Random walk with restart on large graphs using block elimination. ACM Transactions on Database Systems (TODS), 41(2):1--43, 2016."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.26"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.121"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5220\/0006173704990508"},{"key":"e_1_3_2_2_39_1","first-page":"1","article-title":"Connected components on distributed memory machines","volume":"30","author":"Krishnamurthy A.","year":"1997","unstructured":"A. Krishnamurthy, S. Lumetta, D. E. Culler, and K. Yelick. Connected components on distributed memory machines. Third DIMACS Implementation Challenge, 30:1--21, 1997.","journal-title":"Third DIMACS Implementation Challenge"},{"key":"e_1_3_2_2_40_1","first-page":"31","volume-title":"10th USENIX Symposium on Operating Systems Design and Implementation (OSDI)","author":"Kyrola A.","year":"2012","unstructured":"A. Kyrola, G. Blelloch, and C. Guestrin. GraphChi: Large-scale graph computation on just a PC. In 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 31--46, 2012."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13186-3_53"},{"key":"e_1_3_2_2_42_1","volume-title":"The dynamics of viral marketing. ACM Transactions on the Web (TWEB), 1(1):5","author":"Leskovec J.","year":"2007","unstructured":"J. Leskovec, L. A. Adamic, and B. A. Huberman. The dynamics of viral marketing. ACM Transactions on the Web (TWEB), 1(1):5, 2007."},{"key":"e_1_3_2_2_43_1","unstructured":"J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data 2014."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2320716"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/35021BIGCOMP.2015.7072830"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-016-0393-1"},{"key":"e_1_3_2_2_47_1","first-page":"285","volume-title":"15th USENIX Conference on File and Storage Technologies (FAST)","author":"Liu H.","year":"2017","unstructured":"H. Liu and H. H. Huang. Graphene: Fine-grained I\/O management for graph computing. In 15th USENIX Conference on File and Storage Technologies (FAST), pages 285--300, 2017."},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064191"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113298"},{"key":"e_1_3_2_2_50_1","first-page":"548","volume-title":"Advances in Neural Information Processing Systems (NIPS)","volume":"2012","author":"McAuley J. J.","year":"2012","unstructured":"J. J. McAuley and J. Leskovec. Learning to discover social circles in ego networks. In Advances in Neural Information Processing Systems (NIPS), volume 2012, pages 548--56, 2012."},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48054-0_39"},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.0020173"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983551"},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310546"},{"key":"e_1_3_2_2_56_1","volume-title":"Otakar Borruvka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discrete Math, 233(1--3):3--36","author":"Nevsetvril J.","year":"2001","unstructured":"J. Nevsetvril, E. Milkov\u00e1, and H. Nevsetvrilov\u00e1. Otakar Borruvka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discrete Math, 233(1--3):3--36, 2001."},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.213959.116"},{"key":"e_1_3_2_2_58_1","volume-title":"OpenMP Application Programming Interface","author":"Architecture Review Board MP","year":"2018","unstructured":"OpenMP Architecture Review Board. OpenMP Application Programming Interface, 5th edition, 2018.","edition":"5"},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457313"},{"key":"e_1_3_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389081"},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/98267.98287"},{"key":"e_1_3_2_2_62_1","volume-title":"Mapping the gnutella network: Properties of large-scale peer-to-peer systems and implications for system design. arXiv preprint cs\/0209028","author":"Ripeanu M.","year":"2002","unstructured":"M. Ripeanu, I. Foster, and A. Iamnitchi. Mapping the gnutella network: Properties of large-scale peer-to-peer systems and implications for system design. arXiv preprint cs\/0209028, 2002."},{"key":"e_1_3_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/2888116.2888372"},{"key":"e_1_3_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_3_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-58667-0_6"},{"key":"e_1_3_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-43659-3_24"},{"key":"e_1_3_2_2_68_1","volume-title":"GraphZeppelin: Storage-friendly sketching for connected components on dynamic graph streams. arXiv preprint arXiv:2203.14927","author":"Tench D.","year":"2022","unstructured":"D. Tench, E. West, V. Zhang, M. A. Bender, A. Chowdhury, J. A. Dellas, M. Farach-Colton, T. Seip, and K. Zhang. GraphZeppelin: Storage-friendly sketching for connected components on dynamic graph streams. arXiv preprint arXiv:2203.14927, 2022."},{"key":"e_1_3_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/1687399.1687477"},{"key":"e_1_3_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_3_2_2_72_1","first-page":"429","volume-title":"2019 USENIX Annual Technical Conference (USENIX ATC)","author":"Vora K.","year":"2019","unstructured":"K. Vora. LUMOS: Dependency-Driven disk-based graph processing. In 2019 USENIX Annual Technical Conference (USENIX ATC), pages 429--442, 2019."},{"key":"e_1_3_2_2_73_1","first-page":"507","volume-title":"2016 USENIX Annual Technical Conference (USENIX ATC)","author":"Vora K.","year":"2016","unstructured":"K. Vora, G. Xu, and R. Gupta. Load the edges you need: A generic I\/O optimization for disk-based graph processing. In 2016 USENIX Annual Technical Conference (USENIX ATC), pages 507--522, 2016."},{"key":"e_1_3_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00541-4"},{"key":"e_1_3_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-169"},{"key":"e_1_3_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2518664"},{"key":"e_1_3_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/3296957.3173208"},{"key":"e_1_3_2_2_78_1","first-page":"45","volume-title":"13th USENIX Conference on File and Storage Technologies (FAST)","author":"Zheng D.","year":"2015","unstructured":"D. Zheng, D. Mhembere, R. Burns, J. Vogelstein, C. E. Priebe, and A. S. Szalay. FlashGraph: Processing billion-node graphs on an array of commodity SSDs. In 13th USENIX Conference on File and Storage Technologies (FAST), pages 45--58, 2015."},{"key":"e_1_3_2_2_79_1","first-page":"375","volume-title":"USENIX Annual Technical Conference (USENIX ATC)","author":"Zhu X.","year":"2015","unstructured":"X. Zhu, W. Han, and W. Chen. GridGraph: Large-scale graph processing on a single machine using 2-level hierarchical partitioning. In USENIX Annual Technical Conference (USENIX ATC), pages 375--386, 2015."}],"event":{"name":"SIGMOD\/PODS '22: International Conference on Management of Data","location":"Philadelphia PA USA","acronym":"SIGMOD\/PODS '22","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2022 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514221.3526146","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514221.3526146","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514221.3526146","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:13Z","timestamp":1750183813000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514221.3526146"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,10]]},"references-count":78,"alternative-id":["10.1145\/3514221.3526146","10.1145\/3514221"],"URL":"https:\/\/doi.org\/10.1145\/3514221.3526146","relation":{},"subject":[],"published":{"date-parts":[[2022,6,10]]},"assertion":[{"value":"2022-06-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}