{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:35Z","timestamp":1750220555569,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,6,2]],"date-time":"2021-06-02T00:00:00Z","timestamp":1622592000000},"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":["SIGOPS Oper. Syst. Rev."],"published-print":{"date-parts":[[2021,6,2]]},"abstract":"<jats:p>Graph analytics systems must analyze graphs with billions of vertices and edges which require several terabytes of storage. Distributed-memory clusters are often used for analyzing such large graphs since the main memory of a single machine is usually restricted to a few hundreds of gigabytes. This requires partitioning the graph among the machines in the cluster. Existing graph analytics systems use a built-in partitioner that incorporates a particular partitioning policy, but the best policy is dependent on the algorithm, input graph, and platform. Therefore, built-in partitioners are not sufficiently flexible. Stand-alone graph partitioners are available, but they too implement only a few policies.<\/jats:p>\n          <jats:p>CuSP is a fast streaming edge partitioning framework which permits users to specify the desired partitioning policy at a high level of abstraction and quickly generates highquality graph partitions. For example, it can partition wdc12, the largest publicly available web-crawl graph with 4 billion vertices and 129 billion edges, in under 2 minutes for clusters with 128 machines. Our experiments show that it can produce quality partitions 6\u00d7 faster on average than the state-of-theart stand-alone partitioner in the literature while supporting a wider range of partitioning policies.<\/jats:p>","DOI":"10.1145\/3469379.3469385","type":"journal-article","created":{"date-parts":[[2021,6,6]],"date-time":"2021-06-06T12:43:56Z","timestamp":1622983436000},"page":"47-60","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["CuSP"],"prefix":"10.1145","volume":"55","author":[{"given":"Loc","family":"Hoang","sequence":"first","affiliation":[{"name":"The University of Texas at Austin, Austin, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roshan","family":"Dathathri","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gurbinder","family":"Gill","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keshav","family":"Pingali","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/www.graph500.org.  http:\/\/www.graph500.org."},{"volume-title":"WWW","year":"2014","author":"Boldi Paolo","key":"e_1_2_1_2_1"},{"volume-title":"WWW","year":"2011","author":"Boldi Paolo","key":"e_1_2_1_3_1"},{"volume-title":"WWW","year":"2004","author":"Boldi Paolo","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503293"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/PDP.2014.63"},{"key":"e_1_2_1_7_1","series-title":"SIAM J. Sci. Comput","volume-title":"On Two-Dimensional Sparse Matrix Partitioning: Models, Methods, and a Recipe","author":"\u00c7ataly\u00fcrek \u00dcmit V.","year":"2010"},{"volume-title":"Haibo Chen. PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs. EuroSys '15","year":"2015","author":"Chen Rong","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00107"},{"volume-title":"PLDI","year":"2018","author":"Dathathri Roshan","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","series-title":"PVLDB","volume-title":"A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms","author":"Gill Gurbinder","year":"2018"},{"volume-title":"http:\/\/giraph.apache.org\/","year":"2013","author":"Giraph Apache","key":"e_1_2_1_12_1"},{"volume-title":"Carlos Guestrin. PowerGraph: Distributed Graph-parallel Computation on Natural Graphs. OSDI'12","year":"2012","author":"Gonzalez Joseph E.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904486"},{"volume-title":"A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs","series-title":"SIAM J. Sci. Comput","author":"Karypis George","key":"e_1_2_1_15_1"},{"volume-title":"Introduction to Parallel Computing: Design and Analysis of Algorithms","year":"1994","author":"Kumar Vipin","key":"e_1_2_1_16_1"},{"volume-title":"Mach. Learn. Res.","year":"2010","author":"Leskovec Jure","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.153"},{"key":"e_1_2_1_20_1","first-page":"685","volume-title":"Heiko Geppert, Larissa Laich, Lukas Rieger, and Kurt Rothermel. Adwise: Adaptive window-based streaming edge partitioning for high-speed graph processing.","author":"Mayer Christian","year":"2018"},{"volume-title":"Web Data Commons","year":"2012","author":"Meusel Robert","key":"e_1_2_1_21_1"},{"volume-title":"Keshav Pingali. A Lightweight Infrastructure for Graph Analytics. SOSP '13","author":"Nguyen Donald","key":"e_1_2_1_22_1"},{"volume-title":"Giorgio Iacoboni. HDRF: Stream- Based Partitioning for Power-Law Graphs. CIKM '15","year":"2015","author":"Petroni Fabio","key":"e_1_2_1_23_1"},{"volume-title":"The ClueWeb12 Dataset","year":"2013","author":"Project The Lemur","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.59"},{"volume-title":"PuLP: Scalable multi-objective multi-constraint partitioning for small-world networks","year":"2014","author":"Slota G. M.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2017.95"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093338.3093385"},{"volume-title":"Milan Vojnovic. FENNEL: Streaming Graph Partitioning for Massive Scale Graphs. WSDM '14","year":"2014","author":"Tsourakakis Charalampos","key":"e_1_2_1_30_1"},{"volume-title":"Ugander and Lars Backstrom. Balanced Label Propagation for Partitioning Massive Graphs. WSDM '13","year":"2013","author":"Johan","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816682"},{"volume-title":"NIPS.","year":"2014","author":"Xie Cong","key":"e_1_2_1_33_1"},{"volume-title":"Xiaosong Ma. Gemini: A Computation-centric Distributed Graph Processing System. OSDI'16","year":"2016","author":"Zhu Xiaowei","key":"e_1_2_1_34_1"}],"container-title":["ACM SIGOPS Operating Systems Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3469379.3469385","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3469379.3469385","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:23Z","timestamp":1750195703000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3469379.3469385"}},"subtitle":["A Customizable Streaming Edge Partitioner for Distributed Graph Analytics"],"short-title":[],"issued":{"date-parts":[[2021,6,2]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6,2]]}},"alternative-id":["10.1145\/3469379.3469385"],"URL":"https:\/\/doi.org\/10.1145\/3469379.3469385","relation":{},"ISSN":["0163-5980"],"issn-type":[{"type":"print","value":"0163-5980"}],"subject":[],"published":{"date-parts":[[2021,6,2]]},"assertion":[{"value":"2021-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}