{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T04:40:59Z","timestamp":1773895259972,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,8]]},"abstract":"<jats:p>We present Scalable Host-tree Embeddings for Efficient Partitioning (Sheep), a distributed graph partitioning algorithm capable of handling graphs that far exceed main memory. Sheep produces high quality edge partitions an order of magnitude faster than both state of the art offline (e.g., METIS) and streaming partitioners (e.g., Fennel). Sheep's partitions are independent of the input graph distribution, which means that graph elements can be assigned to processing nodes arbitrarily without affecting the partition quality.<\/jats:p>\n          <jats:p>Sheep transforms the input graph into a strictly smaller elimination tree via a distributed map-reduce operation. By partitioning this tree, Sheep finds an upper-bounded communication volume partitioning of the original graph.<\/jats:p>\n          <jats:p>We describe the Sheep algorithm and analyze its space-time requirements, partition quality, and intuitive characteristics and limitations. We compare Sheep to contemporary partitioners and demonstrate that Sheep creates competitive partitions, scales to larger graphs, and has better runtime.<\/jats:p>","DOI":"10.14778\/2824032.2824046","type":"journal-article","created":{"date-parts":[[2015,9,16]],"date-time":"2015-09-16T12:18:17Z","timestamp":1442405897000},"page":"1478-1489","source":"Crossref","is-referenced-by-count":64,"title":["A scalable distributed graph partitioner"],"prefix":"10.14778","volume":"8","author":[{"given":"Daniel","family":"Margo","sequence":"first","affiliation":[{"name":"Harvard University, Cambridge, Massachusetts"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Margo","family":"Seltzer","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, Massachusetts"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,8]]},"reference":[{"issue":"6794","key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1038\/35019019","article-title":"Error and attack tolerance of complex networks","volume":"406","author":"Albert R.","year":"2000","unstructured":"R. Albert , H. Jeong , and A.-L. Barab\u00e1si . Error and attack tolerance of complex networks . Nature , 406 ( 6794 ): 378 -- 382 , 2000 . R. Albert, H. Jeong, and A.-L. Barab\u00e1si. Error and attack tolerance of complex networks. Nature, 406(6794):378--382, 2000.","journal-title":"Nature"},{"key":"e_1_2_1_2_1","volume-title":"ACM International Conference on Information and Knowledge Management","author":"Arifuzzaman S.","year":"2013","unstructured":"S. Arifuzzaman , M. Khan , and M. Marathe . Patric: A parallel algorithm for counting triangles in massive networks . In ACM International Conference on Information and Knowledge Management , 2013 . 10.1145\/2505515.2505545 S. Arifuzzaman, M. Khan, and M. Marathe. Patric: A parallel algorithm for counting triangles in massive networks. In ACM International Conference on Information and Knowledge Management, 2013. 10.1145\/2505515.2505545"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896299081"},{"key":"e_1_2_1_4_1","volume-title":"Hadoop Summit","author":"Avery C.","year":"2011","unstructured":"C. Avery . Giraph : Large-scale graph processing infrastructure on hadoop . Hadoop Summit , 2011 . C. Avery. Giraph: Large-scale graph processing infrastructure on hadoop. Hadoop Summit, 2011."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9312-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480506.1480511"},{"key":"e_1_2_1_8_1","first-page":"1456","volume-title":"20th ACM International Conference on Knowledge Discovery and Data mining","author":"Bourse F.","year":"2014","unstructured":"F. Bourse , M. Lelarge , and M. Vojnovic . Balanced graph edge partition . In 20th ACM International Conference on Knowledge Discovery and Data mining , pages 1456 -- 1465 . ACM, 2014 . 10.1145\/2623330.2623660 F. Bourse, M. Lelarge, and M. Vojnovic. Balanced graph edge partition. In 20th ACM International Conference on Knowledge Discovery and Data mining, pages 1456--1465. ACM, 2014. 10.1145\/2623330.2623660"},{"key":"e_1_2_1_9_1","volume-title":"10th ACM SIGOPS European Conference on Computer Systems. ACM, 2015","author":"Chen R.","year":"1948","unstructured":"R. Chen , J. Shi , Y. Chen , and H. Chen . Powerlyra: Differentiated graph computation and partitioning on skewed graphs . In 10th ACM SIGOPS European Conference on Computer Systems. ACM, 2015 . 10.1145\/274 1948 .2741970 R. Chen, J. Shi, Y. Chen, and H. Chen. Powerlyra: Differentiated graph computation and partitioning on skewed graphs. In 10th ACM SIGOPS European Conference on Computer Systems. ACM, 2015. 10.1145\/2741948.2741970"},{"key":"e_1_2_1_10_1","volume-title":"K-core organization of complex networks. Physical review letters, 96(4):040601","author":"Dorogovtsev S. N.","year":"2006","unstructured":"S. N. Dorogovtsev , A. V. Goltsev , and J. F. F. Mendes . K-core organization of complex networks. Physical review letters, 96(4):040601 , 2006 . S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes. K-core organization of complex networks. Physical review letters, 96(4):040601, 2006."},{"key":"e_1_2_1_11_1","first-page":"345","volume-title":"21st ACM Symposium on Theory of Computing","author":"Fredman M.","year":"1989","unstructured":"M. Fredman and M. Saks . The cell probe complexity of dynamic data structures . In 21st ACM Symposium on Theory of Computing , pages 345 -- 354 . ACM, 1989 . 10.1145\/73007.73040 M. Fredman and M. Saks. The cell probe complexity of dynamic data structures. In 21st ACM Symposium on Theory of Computing, pages 345--354. ACM, 1989. 10.1145\/73007.73040"},{"issue":"2","key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1137\/0710032","article-title":"Nested dissection of a regular finite element mesh","volume":"10","author":"George A.","year":"1973","unstructured":"A. George . Nested dissection of a regular finite element mesh . SIAM Journal on Numerical Analysis , 10 ( 2 ): 345 -- 363 , 1973 . A. George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2):345--363, 1973.","journal-title":"SIAM Journal on Numerical Analysis"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1031001"},{"key":"e_1_2_1_14_1","first-page":"2","volume-title":"Operating Systems Design and Implementation","volume":"12","author":"Gonzalez J. E.","year":"2012","unstructured":"J. E. Gonzalez , Y. Low , H. Gu , D. Bickson , and C. Guestrin . Powergraph: Distributed graph-parallel computation on natural graphs . In Operating Systems Design and Implementation , volume 12 , page 2 , 2012 . J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. Powergraph: Distributed graph-parallel computation on natural graphs. In Operating Systems Design and Implementation, volume 12, page 2, 2012."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.003"},{"key":"e_1_2_1_16_1","first-page":"1","volume-title":"Conference on Innovative Data systems Research","volume":"3","author":"Idreos S.","year":"2007","unstructured":"S. Idreos , M. L. Kersten , and S. Manegold . Database cracking . In Conference on Innovative Data systems Research , volume 3 , pages 1 -- 8 , 2007 . S. Idreos, M. L. Kersten, and S. Manegold. Database cracking. In Conference on Innovative Data systems Research, volume 3, pages 1--8, 2007."},{"issue":"4","key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"e59613","DOI":"10.1371\/journal.pone.0059613","article-title":"Attack robustness and centrality of complex networks","volume":"8","author":"Iyer S.","year":"2013","unstructured":"S. Iyer , T. Killingback , B. Sundaram , and Z. Wang . Attack robustness and centrality of complex networks . PloS ONE , 8 ( 4 ): e59613 , 2013 . S. Iyer, T. Killingback, B. Sundaram, and Z. Wang. Attack robustness and centrality of complex networks. PloS ONE, 8(4):e59613, 2013.","journal-title":"PloS ONE"},{"key":"e_1_2_1_18_1","volume-title":"A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices","author":"Karypis G.","year":"2013","unstructured":"G. Karypis . A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices . University of Minnesota , Department of Computer Science and Engineering, Minneapolis, MN, 2013 . G. Karypis. A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. University of Minnesota, Department of Computer Science and Engineering, Minneapolis, MN, 2013."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1403"},{"issue":"1","key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1137\/0206012","article-title":"A linear tree partitioning algorithm","volume":"6","author":"Kundu S.","year":"1977","unstructured":"S. Kundu and J. Misra . A linear tree partitioning algorithm . SIAM Journal on Computing , 6 ( 1 ): 151 -- 154 , 1977 . S. Kundu and J. Misra. A linear tree partitioning algorithm. SIAM Journal on Computing, 6(1):151--154, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_2_1_22_1","first-page":"31","volume-title":"Operating Systems Design and Implementation","volume":"12","author":"Kyrola A.","year":"2012","unstructured":"A. Kyrola , G. E. Blelloch , and C. Guestrin . Graphchi: Large-scale graph computation on just a pc . In Operating Systems Design and Implementation , volume 12 , pages 31 -- 46 , 2012 . A. Kyrola, G. E. Blelloch, and C. Guestrin. Graphchi: Large-scale graph computation on just a pc. In Operating Systems Design and Implementation, volume 12, pages 31--46, 2012."},{"key":"e_1_2_1_23_1","unstructured":"J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014.  J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014."},{"key":"e_1_2_1_24_1","volume-title":"International Conference on Data Engineering. IEEE","author":"Macko P.","year":"2015","unstructured":"P. Macko , V. J. Marathe , D. W. Margo , and M. I. Seltzer . Llama: Efficient graph analytics using large multiversioned arrays . In International Conference on Data Engineering. IEEE , 2015 . P. Macko, V. J. Marathe, D. W. Margo, and M. I. Seltzer. Llama: Efficient graph analytics using large multiversioned arrays. In International Conference on Data Engineering. IEEE, 2015."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/1807167.1807184","volume-title":"2010 ACM SIGMOD International Conference on Management of Data","author":"Malewicz G.","year":"2010","unstructured":"G. Malewicz , M. H. Austern , A. J. Bik , J. C. Dehnert , I. Horn , N. Leiser , and G. Czajkowski . Pregel: a system for large-scale graph processing . In 2010 ACM SIGMOD International Conference on Management of Data , pages 135 -- 146 . ACM, 2010 . 10.1145\/1807167.1807184 G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In 2010 ACM SIGMOD International Conference on Management of Data, pages 135--146. ACM, 2010. 10.1145\/1807167.1807184"},{"key":"e_1_2_1_26_1","first-page":"563","volume-title":"International Conference on Big Data","author":"Miao H.","year":"2013","unstructured":"H. Miao , X. Liu , B. Huang , and L. Getoor . A hypergraph-partitioned vertex programming approach for large-scale consensus optimization . In International Conference on Big Data , pages 563 -- 568 . IEEE, 2013 . H. Miao, X. Liu, B. Huang, and L. Getoor. A hypergraph-partitioned vertex programming approach for large-scale consensus optimization. In International Conference on Big Data, pages 563--568. IEEE, 2013."},{"key":"e_1_2_1_27_1","volume-title":"Introducing the graph 500","author":"Murphy R. C.","year":"2010","unstructured":"R. C. Murphy , K. B. Wheeler , B. W. Barrett , and J. A. Ang . Introducing the graph 500 . Cray User's Group (CUG) , 2010 . R. C. Murphy, K. B. Wheeler, B. W. Barrett, and J. A. Ang. Introducing the graph 500. Cray User's Group (CUG), 2010."},{"issue":"2","key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1073\/pnas.98.2.404","article-title":"The structure of scientific collaboration networks","volume":"98","author":"Newman M. E.","year":"2001","unstructured":"M. E. Newman . The structure of scientific collaboration networks . Proceedings of the National Academy of Sciences , 98 ( 2 ): 404 -- 409 , 2001 . M. E. Newman. The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences, 98(2):404--409, 2001.","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"2","key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1137\/1003021","article-title":"The use of linear graphs in gauss elimination","volume":"3","author":"Parter S.","year":"1961","unstructured":"S. Parter . The use of linear graphs in gauss elimination . SIAM Review , 3 ( 2 ): 119 -- 130 , 1961 . S. Parter. The use of linear graphs in gauss elimination. SIAM Review, 3(2):119--130, 1961.","journal-title":"SIAM Review"},{"key":"e_1_2_1_30_1","first-page":"59","volume-title":"Handbook on Data Structures and Applications","author":"Pothen A.","year":"2004","unstructured":"A. Pothen and S. Toledo . Elimination structures in scientific computing . Handbook on Data Structures and Applications , pages 59 -- 51 , 2004 . A. Pothen and S. Toledo. Elimination structures in scientific computing. Handbook on Data Structures and Applications, pages 59--1, 2004."},{"key":"e_1_2_1_31_1","first-page":"41","volume-title":"USENIX Annual Technical Conference","author":"Prabhakaran V.","year":"2012","unstructured":"V. Prabhakaran , M. Wu , X. Weng , F. McSherry , L. Zhou , and M. Haradasan . Managing large graphs on multi-cores with graph awareness . In USENIX Annual Technical Conference , pages 41 -- 52 , 2012 . V. Prabhakaran, M. Wu, X. Weng, F. McSherry, L. Zhou, and M. Haradasan. Managing large graphs on multi-cores with graph awareness. In USENIX Annual Technical Conference, pages 41--52, 2012."},{"key":"e_1_2_1_32_1","first-page":"472","volume-title":"24th ACM Symposium on Operating Systems Principles","author":"Roy A.","year":"2013","unstructured":"A. Roy , I. Mihailovic , and W. Zwaenepoel . X-stream: Edge-centric graph processing using streaming partitions . In 24th ACM Symposium on Operating Systems Principles , pages 472 -- 488 . ACM, 2013 . 10.1145\/2517349.2522740 A. Roy, I. Mihailovic, and W. Zwaenepoel. X-stream: Edge-centric graph processing using streaming partitions. In 24th ACM Symposium on Operating Systems Principles, pages 472--488. ACM, 2013. 10.1145\/2517349.2522740"},{"key":"e_1_2_1_33_1","volume-title":"25th International Conference on Scientific and Statistical Database Management. ACM","author":"Salihoglu S.","year":"2013","unstructured":"S. Salihoglu and J. Widom . Gps: A graph processing system . In 25th International Conference on Scientific and Statistical Database Management. ACM , 2013 . 10.1145\/2484838.2484843 S. Salihoglu and J. Widom. Gps: A graph processing system. In 25th International Conference on Scientific and Statistical Database Management. ACM, 2013. 10.1145\/2484838.2484843"},{"key":"e_1_2_1_34_1","first-page":"979","volume-title":"ACM SIGMOD International Conference on Management of Data","author":"Satish N.","year":"2014","unstructured":"N. Satish , N. Sundaram , M. M. A. Patwary , J. Seo , J. Park , M. A. Hassaan , S. Sengupta , Z. Yin , and P. Dubey . Navigating the maze of graph analytics frameworks using massive graph datasets . In ACM SIGMOD International Conference on Management of Data , pages 979 -- 990 . ACM, 2014 . 10.1145\/2588555.2610518 N. Satish, N. Sundaram, M. M. A. Patwary, J. Seo, J. Park, M. A. Hassaan, S. Sengupta, Z. Yin, and P. Dubey. Navigating the maze of graph analytics frameworks using massive graph datasets. In ACM SIGMOD International Conference on Management of Data, pages 979--990. ACM, 2014. 10.1145\/2588555.2610518"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","first-page":"1222","DOI":"10.1145\/2339530.2339722","volume-title":"18th ACM SIGKDD International Conference on Knowledge Discovery and Data mining","author":"Stanton I.","year":"2012","unstructured":"I. Stanton and G. Kliot . Streaming graph partitioning for large distributed graphs . In 18th ACM SIGKDD International Conference on Knowledge Discovery and Data mining , pages 1222 -- 1230 . ACM, 2012 . 10.1145\/2339530.2339722 I. Stanton and G. Kliot. Streaming graph partitioning for large distributed graphs. In 18th ACM SIGKDD International Conference on Knowledge Discovery and Data mining, pages 1222--1230. ACM, 2012. 10.1145\/2339530.2339722"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/2556195.2556213","volume-title":"7th ACM International Conference on Web Search and Data Mining","author":"Tsourakakis C.","year":"2014","unstructured":"C. Tsourakakis , C. Gkantsidis , B. Radunovic , and M. Vojnovic . Fennel: Streaming graph partitioning for massive scale graphs . In 7th ACM International Conference on Web Search and Data Mining , pages 333 -- 342 . ACM, 2014 . 10.1145\/2556195.2556213 C. Tsourakakis, C. Gkantsidis, B. Radunovic, and M. Vojnovic. Fennel: Streaming graph partitioning for massive scale graphs. In 7th ACM International Conference on Web Search and Data Mining, pages 333--342. ACM, 2014. 10.1145\/2556195.2556213"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2824032.2824046","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:17:46Z","timestamp":1672222666000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2824032.2824046"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8]]},"references-count":36,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["10.14778\/2824032.2824046"],"URL":"https:\/\/doi.org\/10.14778\/2824032.2824046","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,8]]}}}