{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T15:45:35Z","timestamp":1783784735019,"version":"3.55.0"},"reference-count":101,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,9,30]],"date-time":"2018-09-30T00:00:00Z","timestamp":1538265600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61772335 and 61572314"],"award-info":[{"award-number":["61772335 and 61572314"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Key Research 8 Development Program of China","award":["2016YFB1000104"],"award-info":[{"award-number":["2016YFB1000104"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2018,9,30]]},"abstract":"<jats:p>Natural graphs with skewed distributions raise unique challenges to distributed graph computation and partitioning. Existing graph-parallel systems usually use a \u201cone-size-fits-all\u201d design that uniformly processes all vertices, which either suffer from notable load imbalance and high contention for high-degree vertices (e.g., Pregel and GraphLab) or incur high communication cost and memory consumption even for low-degree vertices (e.g., PowerGraph and GraphX). In this article, we argue that skewed distributions in natural graphs also necessitate differentiated processing on high-degree and low-degree vertices. We then introduce PowerLyra, a new distributed graph processing system that embraces the best of both worlds of existing graph-parallel systems. Specifically, PowerLyra uses centralized computation for low-degree vertices to avoid frequent communications and distributes the computation for high-degree vertices to balance workloads. PowerLyra further provides an efficient hybrid graph partitioning algorithm (i.e., hybrid-cut) that combines edge-cut (for low-degree vertices) and vertex-cut (for high-degree vertices) with heuristics. To improve cache locality of inter-node graph accesses, PowerLyra further provides a locality-conscious data layout optimization. PowerLyra is implemented based on the latest GraphLab and can seamlessly support various graph algorithms running in both synchronous and asynchronous execution modes. A detailed evaluation on three clusters using various graph-analytics and MLDM (Machine Learning and Data Mining) applications shows that PowerLyra outperforms PowerGraph by up to 5.53X (from 1.24X) and 3.26X (from 1.49X) for real-world and synthetic graphs, respectively, and is much faster than other systems like GraphX and Giraph, yet with much less memory consumption. A porting of hybrid-cut to GraphX further confirms the efficiency and generality of PowerLyra.<\/jats:p>","DOI":"10.1145\/3298989","type":"journal-article","created":{"date-parts":[[2019,1,23]],"date-time":"2019-01-23T13:02:14Z","timestamp":1548248534000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":117,"title":["PowerLyra"],"prefix":"10.1145","volume":"5","author":[{"given":"Rong","family":"Chen","sequence":"first","affiliation":[{"name":"Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiaxin","family":"Shi","sequence":"additional","affiliation":[{"name":"Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yanzhe","family":"Chen","sequence":"additional","affiliation":[{"name":"Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Binyu","family":"Zang","sequence":"additional","affiliation":[{"name":"Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haibing","family":"Guan","sequence":"additional","affiliation":[{"name":"Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haibo","family":"Chen","sequence":"additional","affiliation":[{"name":"Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,1,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1898953.1899055"},{"key":"e_1_2_1_2_1","first-page":"143","article-title":"Zipf\u2019s law and the internet","volume":"3","author":"Adamic Lada A.","year":"2002","journal-title":"Glottometrics"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2749246.2749263"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.587"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201913)","author":"Bronson Nathan","year":"2013"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342011403516"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/646010.676990"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/080737770"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129900"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600212.2600233"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741970"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2637166.2637236"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-015-1501-x"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391232"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2703904"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168846"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557049"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_2_1_20_1","volume-title":"The 9th DIMACS Implementation Challenge - Shortest Paths","author":"DIMACS."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741968"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS\u201911)","author":"Gonzalez Joseph","year":"2011"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912)","author":"Gonzalez Joseph E.","year":"2012"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI\u201909)","author":"Gonzalez Joseph E.","year":"2009"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI\u2019 14)","author":"Gonzalez Joseph E.","year":"2014"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592799"},{"key":"e_1_2_1_28_1","unstructured":"Henry Haselgrove. 2010. Wikipedia page-to-page link database. http:\/\/haselgrove.id.au\/wikipedia.htm.  Henry Haselgrove. 2010. Wikipedia page-to-page link database. http:\/\/haselgrove.id.au\/wikipedia.htm."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2524211.2524218"},{"key":"e_1_2_1_30_1","volume-title":"Mining Ecommerce Graph Data with Apache Spark at Alibaba Taobao. Retrieved","author":"Huang Andy","year":"2018"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484429"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159722"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3084446"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612673"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921632.1921634"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144598334138"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465369"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912)","author":"Kyrola Aapo","year":"2012"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807632"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626407002843"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of 2017 USENIX Annual Technical Conference (USENIX ATC\u201917)","author":"Ma Lingxiao","year":"2017"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064191"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of 2017 USENIX Annual Technical Conference (USENIX ATC\u201917)","author":"Malicevic Jasmina","year":"2017"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824046"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/314500.314891"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1080\/00107510500052444"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687569"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465353"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815408"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772778"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2068816.2068825"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484843"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.5555\/646665.698944"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556572"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2467799"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026877.3026902"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2015.8"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920931"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_2_1_69_1","article-title":"Scalable collaborative filtering approaches for large recommender systems","author":"Tak\u00e1cs G\u00e1bor","year":"2009","journal-title":"Journal of Machine Learning Research 10"},{"key":"e_1_2_1_70_1","unstructured":"Tencent. 2018. Design and Practice of the Anomaly Detection Framework for Billions of User in WeChat (in Chinese). https:\/\/cloud.tencent.com\/developer\/article\/1028442.  Tencent. 2018. Design and Practice of the Anomaly Detection Framework for Billions of User in WeChat (in Chinese). https:\/\/cloud.tencent.com\/developer\/article\/1028442."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8257949"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055543"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2017.237"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2017.119"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178508"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2014.58"},{"key":"e_1_2_1_80_1","volume-title":"Proceedings of 2018 USENIX Annual Technical Conference (USENIX ATC\u201918)","author":"Wang Siyuan","year":"2018"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688538"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/1519065.1519089"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806777.2806849"},{"key":"e_1_2_1_84_1","volume-title":"Proceedings of the 14th USENIX Conference on Networked Systems Design and Implementation (NSDI\u201917)","author":"Xiao Wencong","year":"2017"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688508"},{"key":"e_1_2_1_86_1","volume-title":"Proceedings of the 28th Annual Conference on Neural Information Processing Systems (NIPS\u201914)","author":"Xie Cong","year":"2014"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733103"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646301"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2005.4"},{"key":"e_1_2_1_90_1","volume-title":"Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation (NSDI\u201912)","author":"Zaharia Matei","year":"2012"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.5555\/2930583.2930596"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688507"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994511"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026877.3026900"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2018.00053"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132777"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2016.2624289"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556554"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68880-8_32"},{"key":"e_1_2_1_100_1","volume-title":"Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201916)","author":"Zhu Xiaowei","year":"2016"},{"key":"e_1_2_1_101_1","volume-title":"Proceedings of the 2015 USENIX Conference on Annual Technical Conference (USENIX ATC\u201915)","author":"Zhu Xiaowei","year":"2015"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3298989","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3298989","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:12:56Z","timestamp":1750201976000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3298989"}},"subtitle":["Differentiated Graph Computation and Partitioning on Skewed Graphs"],"short-title":[],"issued":{"date-parts":[[2018,9,30]]},"references-count":101,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9,30]]}},"alternative-id":["10.1145\/3298989"],"URL":"https:\/\/doi.org\/10.1145\/3298989","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,30]]},"assertion":[{"value":"2015-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}