{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:36:25Z","timestamp":1750221385377,"version":"3.41.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,3,22]],"date-time":"2018-03-22T00:00:00Z","timestamp":1521676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61702201, 61628204, 61732010 and 61672251"],"award-info":[{"award-number":["61702201, 61628204, 61732010 and 61672251"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Key Research and Development Program of China","award":["2017YFB1001603"],"award-info":[{"award-number":["2017YFB1001603"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>Existing graph processing essentially relies on the underlying iterative execution with synchronous (Sync) and\/or asynchronous (Async) engine. Nevertheless, they both suffer from a wide class of inherent serialization arising from data interdependencies within a graph.<\/jats:p>\n          <jats:p>In this article, we present SymGraph, a judicious graph engine with symbolic iteration that enables the parallelism of dependent computation on vertices. SymGraph allows using abstract symbolic value (instead of the concrete value) for the computation if the desired data is unavailable. To maximize the potential of symbolic iteration, we propose a chain of tailored sophisticated techniques, enabling SymGraph to scale out with a new milestone of efficiency for large-scale graph processing. We evaluate SymGraph in comparison to Sync, Async, and a hybrid of Sync and Async engines. Our results on 12 nodes show that SymGraph outperforms all three graph engines by 1.93x (vs. Sync), 1.98x (vs. Async), and 1.57x (vs. Hybrid) on average. In particular, the performance for PageRank on 32 nodes can be dramatically improved by 16.5x (vs. Sync), 23.3x (vs. Async), and 12.1x (vs. Hybrid), respectively. The efficiency of SymGraph is also validated with at least one order of magnitude improvement in contrast to three specialized graph systems (Naiad, GraphX, and PGX.D).<\/jats:p>","DOI":"10.1145\/3170434","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T12:29:49Z","timestamp":1521808189000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Efficient and Scalable Graph Parallel Processing With Symbolic Execution"],"prefix":"10.1145","volume":"15","author":[{"given":"Long","family":"Zheng","sequence":"first","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7903-2061","authenticated-orcid":false,"given":"Xiaofei","family":"Liao","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hai","family":"Jin","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,3,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623757"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2749469.2750386"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382271"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254766"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884487"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/297805.297827"},{"volume-title":"Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201908)","year":"2008","author":"Cadar Cristian","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741970"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451152"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3020078.3021739"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980258.2980343"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926432"},{"volume-title":"Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS\u201911)","year":"2011","author":"Gonzalez Joseph E.","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912)","year":"2012","author":"Gonzalez Joseph E.","key":"e_1_2_1_15_1"},{"volume-title":"Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201914)","year":"2014","author":"Gonzalez Joseph E.","key":"e_1_2_1_16_1"},{"volume-title":"Proceedings of the 49th Annual IEEE\/ACM International Symposium on Microarchitecture (MICRO\u201916)","author":"Ham T. J.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732980"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.40842"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807620"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1331904.1331905"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2017.150"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/369028.369103"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/360248.360252"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912)","year":"2012","author":"Kyrola Aapo","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/977395.977673"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807632"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/646491.694954"},{"volume-title":"Proceedings of the 11th USENIX Conference on Networked Systems Design and Implementation (NSDI\u201914)","year":"2014","author":"Lim Hyeontaek","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"volume-title":"Proceedings of the International Conference on Uncertainty in Artificial Intelligence (UAI\u201910)","author":"Low Yucheng","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818185"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Lili Mei Heyan Huang Xiaochi Wei and Xianling Mao. 2016. A novel unsupervised method for new word extraction. SCIENCE CHINA Information Sciences 59 9 092102:1--092102:11.  Lili Mei Heyan Huang Xiaochi Wei and Xianling Mao. 2016. A novel unsupervised method for new word extraction. SCIENCE CHINA Information Sciences 59 9 092102:1--092102:11.","DOI":"10.1007\/s11432-015-0906-9"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2145816.2145832"},{"volume-title":"Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI\u201912)","author":"Murphy Kevin P.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847263.2847337"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2016.24"},{"volume-title":"Cyclades: Conflict-free asynchronous machine learning. In Advances in Neural Information Processing Systems 29 (NIPS\u201916). 2568--2576.","year":"2016","author":"Pan Xinghao","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996845"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"volume-title":"Proceedings of the 45th International Conference on Parallel Processing (ICPP\u201916)","author":"Song S.","key":"e_1_2_1_44_1"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376675"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2992784"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688508"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Yu Yao Ning Zhaolong and Guo Lei. 2016. A secure routing scheme based on social network analysis in wireless mesh networks. SCIENCE CHINA Information Sciences 59 12 122310:1--122310:12.  Yu Yao Ning Zhaolong and Guo Lei. 2016. A secure routing scheme based on social network analysis in wireless mesh networks. SCIENCE CHINA Information Sciences 59 12 122310:1--122310:12.","DOI":"10.1007\/s11432-015-5467-7"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3020078.3021737"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1113841.1113842"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2017.98"},{"volume-title":"Proceedings of the 24th IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM\u201916)","author":"Zhou S.","key":"e_1_2_1_55_1"},{"volume-title":"Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201916)","year":"2016","author":"Zhu Xiaowei","key":"e_1_2_1_56_1"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3170434","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3170434","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:57Z","timestamp":1750213617000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3170434"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,22]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3170434"],"URL":"https:\/\/doi.org\/10.1145\/3170434","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2018,3,22]]},"assertion":[{"value":"2017-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}