{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T16:07:11Z","timestamp":1784390831261,"version":"3.55.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:p>We propose Distributed Neighbor Expansion (Distributed NE), a parallel and distributed graph partitioning method that can scale to trillion-edge graphs while providing high partitioning quality. Distributed NE is based on a new heuristic, called parallel expansion, where each partition is constructed in parallel by greedily expanding its edge set from a single vertex in such a way that the increase of the vertex cuts becomes local minimal. We theoretically prove that the proposed method has the upper bound in the partitioning quality. The empirical evaluation with various graphs shows that the proposed method produces higher-quality partitions than the state-of-the-art distributed graph partitioning algorithms. The performance evaluation shows that the space efficiency of the proposed method is an order-of-magnitude better than the existing algorithms, keeping its time efficiency comparable. As a result, Distributed NE can partition a trillion-edge graph using only 256 machines within 70 minutes.<\/jats:p>","DOI":"10.14778\/3358701.3358706","type":"journal-article","created":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T02:58:07Z","timestamp":1599793087000},"page":"2379-2392","source":"Crossref","is-referenced-by-count":47,"title":["Distributed edge partitioning for trillion-edge graphs"],"prefix":"10.14778","volume":"12","author":[{"given":"Masatoshi","family":"Hanai","sequence":"first","affiliation":[{"name":"Southern University of Science and Technology, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Toyotaro","family":"Suzumura","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wen Jun","family":"Tan","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elvis","family":"Liu","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georgios","family":"Theodoropoulos","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wentong","family":"Cai","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apache Giraph. http:\/\/giraph.apache.org.  Apache Giraph. http:\/\/giraph.apache.org."},{"key":"e_1_2_1_2_1","unstructured":"Graph500. https:\/\/graph500.org\/.  Graph500. https:\/\/graph500.org\/."},{"key":"e_1_2_1_3_1","unstructured":"Laboratory for web algorithmics (LWA). http:\/\/law.di.unimi.it\/index.php.  Laboratory for web algorithmics (LWA). http:\/\/law.di.unimi.it\/index.php."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/080737770"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236208"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204035"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480506.1480511"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503293"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623660"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49487-6_4"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741970"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/070710111"},{"key":"e_1_2_1_16_1","first-page":"17","volume-title":"OSDI","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 OSDI , pages 17 -- 30 , 2012 . J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. PowerGraph: Distributed graph-parallel computation on natural graphs. In OSDI, pages 17--30, 2012."},{"key":"e_1_2_1_17_1","first-page":"599","volume-title":"OSDI","author":"Gonzalez J. E.","year":"2014","unstructured":"J. E. Gonzalez , R. S. Xin , A. Dave , D. Crankshaw , M. J. Franklin , and I. Stoica . GraphX: Graph processing in a distributed dataflow framework . In OSDI , pages 599 -- 613 , 2014 . J. E. Gonzalez, R. S. Xin, A. Dave, D. Crankshaw, M. J. Franklin, and I. Stoica. GraphX: Graph processing in a distributed dataflow framework. In OSDI, pages 599--613, 2014."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.49"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732980"},{"key":"e_1_2_1_20_1","first-page":"1","volume-title":"SC","author":"Hong S.","year":"2015","unstructured":"S. Hong , S. Depner , T. Manhardt , J. Van Der Lugt, M. Verstraaten, and H. Chafi. PGX. D: A fast distributed graph processing engine . In SC , pages 58: 1 -- 58 :12, 2015 . S. Hong, S. Depner, T. Manhardt, J. Van Der Lugt, M. Verstraaten, and H. Chafi. PGX. D: A fast distributed graph processing engine. In SC, pages 58:1--58:12, 2015."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904486"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137650"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1403"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465369"},{"key":"e_1_2_1_25_1","first-page":"1","volume-title":"COCOON","author":"Kleinberg J. M.","year":"1999","unstructured":"J. M. Kleinberg , R. Kumar , P. Raghavan , S. Rajagopalan , and A. S. Tomkins . The Web As a Graph: Measurements, Models, and Methods . In COCOON , pages 1 -- 17 , 1999 . J. M. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. S. Tomkins. The Web As a Graph: Measurements, Models, and Methods. In COCOON, pages 1--17, 1999."},{"key":"e_1_2_1_26_1","unstructured":"konect network dataset KONECT. http:\/\/konect.uni-koblenz.de.  konect network dataset KONECT. http:\/\/konect.uni-koblenz.de."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_28_1","first-page":"591","volume-title":"WWW","author":"Kwak H.","year":"2010","unstructured":"H. Kwak , C. Lee , H. Park , and S. Moon . What is twitter, a social network or a news media ? In WWW , pages 591 -- 600 , 2010 . H. Kwak, C. Lee, H. Park, and S. Moon. What is twitter, a social network or a news media? In WWW, pages 591--600, 2010."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1756039"},{"key":"e_1_2_1_30_1","unstructured":"J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data.  J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064191"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824046"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.153"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1397735.1397742"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806424"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732294"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2017.95"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363744"},{"key":"e_1_2_1_44_1","volume-title":"DTI","volume":"1","author":"Takac L.","year":"2012","unstructured":"L. Takac and M. Zabovsky . Data analysis in public social networks . In DTI , volume 1 , 2012 . L. Takac and M. Zabovsky. Data analysis in public social networks. In DTI, volume 1, 2012."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"issue":"1","key":"e_1_2_1_46_1","first-page":"22","article-title":"Efficient breadth-first search on massively parallel and distributed-memory machines","volume":"2","author":"Ueno K.","year":"2017","unstructured":"K. Ueno , T. Suzumura , N. Maruyama , K. Fujisawa , and S. Matsuoka . Efficient breadth-first search on massively parallel and distributed-memory machines . DSE , 2 ( 1 ): 22 -- 35 , 2017 . K. Ueno, T. Suzumura, N. Maruyama, K. Fujisawa, and S. Matsuoka. Efficient breadth-first search on massively parallel and distributed-memory machines. DSE, 2(1):22--35, 2017.","journal-title":"DSE"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055543"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806777.2806849"},{"key":"e_1_2_1_49_1","first-page":"1673","volume-title":"NIPS","author":"Xie C.","year":"2014","unstructured":"C. Xie , L. Yan , W.-J. Li , and Z. Zhang . Distributed power-law graph computing: Theoretical and empirical analysis . In NIPS , pages 1673 -- 1681 , 2014 . C. Xie, L. Yan, W.-J. Li, and Z. Zhang. Distributed power-law graph computing: Theoretical and empirical analysis. In NIPS, pages 1673--1681, 2014."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741096"},{"key":"e_1_2_1_51_1","first-page":"745","volume-title":"ICDM","author":"Yang J.","year":"2012","unstructured":"J. Yang and J. Leskovec . Defining and evaluating network communities based on ground-truth . In ICDM , pages 745 -- 754 , 2012 . J. Yang and J. Leskovec. Defining and evaluating network communities based on ground-truth. In ICDM, pages 745--754, 2012."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063469"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098033"},{"key":"e_1_2_1_55_1","first-page":"301","volume-title":"OSDI","author":"Zhu X.","year":"2016","unstructured":"X. Zhu , W. Chen , W. Zheng , and X. Ma . Gemini: A computation-centric distributed graph processing system . In OSDI , pages 301 -- 316 , 2016 . X. Zhu, W. Chen, W. Zheng, and X. Ma. Gemini: A computation-centric distributed graph processing system. In OSDI, pages 301--316, 2016."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3358701.3358706","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:54:17Z","timestamp":1672221257000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3358701.3358706"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":55,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["10.14778\/3358701.3358706"],"URL":"https:\/\/doi.org\/10.14778\/3358701.3358706","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}