{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:49:19Z","timestamp":1773481759936,"version":"3.50.1"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,10]]},"abstract":"<jats:p>\n            Graph processing systems are important in the big data domain. However, processing graphs in parallel often introduces redundant computations in existing algorithms and models. Prior work has proposed techniques to optimize redundancies for out-of-core graph systems, rather than distributed graph systems. In this paper, we study various state-of-the-art distributed graph systems and observe root causes for these pervasively existing redundancies. To reduce redundancies without sacrificing parallelism, we further propose\n            <jats:italic>SLFE,<\/jats:italic>\n            a distributed graph processing system, designed with the principle of \"start late or finish early\".\n            <jats:italic>SLFE<\/jats:italic>\n            employs a novel preprocessing stage to obtain a graph's topological knowledge with negligible overhead.\n            <jats:italic>SLFE's<\/jats:italic>\n            redundancy-aware vertex-centric computation model can then utilize such knowledge to reduce the redundant computations at runtime.\n            <jats:italic>SLFE<\/jats:italic>\n            also provides a set of APIs to improve programmability. Our experiments on an 8-machine high-performance cluster show that\n            <jats:italic>SLFE<\/jats:italic>\n            outperforms all well-known distributed graph processing systems with the inputs of real-world graphs, yielding up to 75x speedup. Moreover,\n            <jats:italic>SLFE<\/jats:italic>\n            outperforms two state-of-the-art shared memory graph systems on a high-end machine with up to 1644x speedup.\n            <jats:italic>SLFE's<\/jats:italic>\n            redundancy-reduction schemes are generally applicable to other vertex-centric graph processing systems.\n          <\/jats:p>","DOI":"10.14778\/3282495.3282501","type":"journal-article","created":{"date-parts":[[2019,1,4]],"date-time":"2019-01-04T13:35:28Z","timestamp":1546608928000},"page":"154-168","source":"Crossref","is-referenced-by-count":19,"title":["&lt;u&gt;S&lt;\/u&gt;tart &lt;u&gt;l&lt;\/u&gt;ate or &lt;u&gt;f&lt;\/u&gt;inish &lt;u&gt;e&lt;\/u&gt;arly"],"prefix":"10.14778","volume":"12","author":[{"given":"Shuang","family":"Song","sequence":"first","affiliation":[{"name":"University of Texas at Austin"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xu","family":"Liu","sequence":"additional","affiliation":[{"name":"College of William and Mary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qinzhe","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Texas at Austin"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Gerstlauer","sequence":"additional","affiliation":[{"name":"University of Texas at Austin"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao","family":"Li","sequence":"additional","affiliation":[{"name":"University of Florida"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lizy K.","family":"John","sequence":"additional","affiliation":[{"name":"University of Texas at Austin"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"The github repository for the appendix of Start Late or Finish Early: A Distributed Graph Processing System with Redundancy Reduction. https:\/\/github.com\/songshuangVLDB19\/VLDB19_Appendix.  The github repository for the appendix of Start Late or Finish Early: A Distributed Graph Processing System with Redundancy Reduction. https:\/\/github.com\/songshuangVLDB19\/VLDB19_Appendix."},{"key":"e_1_2_1_2_1","unstructured":"Ieee standard for floating-point arithmetic. IEEE Std 754-2008 pages 1--70 Aug 2008.  Ieee standard for floating-point arithmetic. IEEE Std 754-2008 pages 1--70 Aug 2008."},{"key":"e_1_2_1_3_1","volume-title":"https:\/\/software.intel.com\/en-us\/articles\/intel-performance-counter-monitor#abstracting","year":"2012"},{"key":"e_1_2_1_4_1","volume-title":"https:\/\/issues.apache.org\/jira\/browse\/SPARK-3427","year":"2014"},{"key":"e_1_2_1_5_1","volume-title":"Feb.","year":"2018"},{"key":"e_1_2_1_6_1","volume-title":"https:\/\/perf.wiki.kernel.org\/index.php\/Main_Page","year":"2018"},{"key":"e_1_2_1_7_1","first-page":"125","volume-title":"2017 USENIX Annual Technical Conference (USENIX ATC 17)","author":"Ai Z.","year":"2017"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10596-3_6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.86"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36727-4_14"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389013"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0107"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342011403516"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/978-3-642-96868-6","volume-title":"Catalogue of Artificial Intelligence Tools","author":"Bundy A.","year":"1984"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600212.2600233"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741970"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2008.88"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.39"},{"key":"e_1_2_1_22_1","volume-title":"USA","author":"Forum M. P.","year":"1994"},{"key":"e_1_2_1_23_1","first-page":"17","volume-title":"Presented as part of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12)","author":"Gonzalez J. E.","year":"2012"},{"key":"e_1_2_1_24_1","first-page":"599","volume-title":"11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14)","author":"Gonzalez J. E.","year":"2014"},{"key":"e_1_2_1_25_1","unstructured":"D. Gregor and A. Lumsdaine. The parallel bgl: A generic library for distributed graph computations.  D. Gregor and A. Lumsdaine. The parallel bgl: A generic library for distributed graph computations."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2777598.2777604"},{"key":"e_1_2_1_27_1","first-page":"14","volume-title":"Proceedings of the 7th USENIX Conference on Hot Topics in Cloud Computing, HotCloud'15","author":"Heintz B.","year":"2015"},{"key":"e_1_2_1_28_1","volume-title":"Methods of applied mathematics","author":"Hildebrand F. B.","year":"2012"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2150976.2151013"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00117"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465369"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2015.15"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2907294.2907312"},{"key":"e_1_2_1_35_1","first-page":"31","volume-title":"Presented as part of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12)","author":"Kyrola A.","year":"2012"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807632"},{"key":"e_1_2_1_37_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_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735517"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2925426.2926287"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851183"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2016.24"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815408"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484843"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007265"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915238"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2467799"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2016.16"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2016.7840840"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809983"},{"key":"e_1_2_1_57_1","volume-title":"The anatomy of the facebook social graph. arXiv preprint arXiv:1111.4503","author":"Ugander J.","year":"2011"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055543"},{"key":"e_1_2_1_59_1","first-page":"507","volume-title":"2016 USENIX Annual Technical Conference (USENIX ATC 16)","author":"Vora K.","year":"2016"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851154"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688508"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741096"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026877.3026900"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809987"},{"key":"e_1_2_1_65_1","first-page":"301","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)","author":"Zhu X.","year":"2016"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3282495.3282501","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:32:13Z","timestamp":1672223533000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3282495.3282501"}},"subtitle":["a distributed graph processing system with redundancy reduction"],"short-title":[],"issued":{"date-parts":[[2018,10]]},"references-count":65,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["10.14778\/3282495.3282501"],"URL":"https:\/\/doi.org\/10.14778\/3282495.3282501","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,10]]}}}