{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:10:13Z","timestamp":1782969013075,"version":"3.54.5"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,4]]},"abstract":"<jats:p>\n            This paper presents\n            <jats:italic>LA3<\/jats:italic>\n            , a scalable distributed system for graph analytics. LA3 couples a vertex-based programming model with a highly optimized linear algebra-based engine. It translates any vertex-centric program into an iteratively executed sparse matrix-vector multiplication (SpMV). To reduce communication and enhance scalability, the adjacency matrix representing an input graph is partitioned into locality-aware 2D tiles distributed across multiple processes. Alongside, three major optimizations are incorporated to preclude redundant computations and minimize communication. First, the link-based structure of the input graph is exploited to classify vertices into different types. Afterwards, vertices of special types are factored out of the main loop of the graph application to avoid superfluous computations. We refer to this novel optimization as\n            <jats:italic>computation filtering.<\/jats:italic>\n            Second, a\n            <jats:italic>communication filtering<\/jats:italic>\n            mechanism is involved to optimize for the high sparsity of the input matrix due to power-law distributions, common in real-world graphs. This optimization ensures that each process receives only the messages that pertain to non-zero entries in its tiles, substantially reducing communication traffic since most tiles are highly sparse. Lastly, a\n            <jats:italic>pseudo-asynchronous computation and communication<\/jats:italic>\n            optimization is proposed, whereby processes progress and communicate asynchronously, consume messages as soon as they become available, and block otherwise. We implemented and extensively tested LA3 on private and public clouds. Results show that LA3 outperforms six related state-of-the-art and popular distributed graph analytics systems by an average of 10X.\n          <\/jats:p>","DOI":"10.14778\/3204028.3204035","type":"journal-article","created":{"date-parts":[[2018,5,22]],"date-time":"2018-05-22T19:56:10Z","timestamp":1527018970000},"page":"920-933","source":"Crossref","is-referenced-by-count":14,"title":["LA3"],"prefix":"10.14778","volume":"11","author":[{"given":"Yousuf","family":"Ahmad","sequence":"first","affiliation":[{"name":"Carnegie Mellon University in Qatar"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Omar","family":"Khattab","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University in Qatar"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arsal","family":"Malik","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University in Qatar"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ahmad","family":"Musleh","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University in Qatar"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad","family":"Hammoud","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University in Qatar"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mucahid","family":"Kutlu","sequence":"additional","affiliation":[{"name":"Qatar University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mostafa","family":"Shehata","sequence":"additional","affiliation":[{"name":"Qatar University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tamer","family":"Elsayed","sequence":"additional","affiliation":[{"name":"Qatar University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"http:\/\/giraph.apache.org\/","author":"Giraph Apache","year":"2017","unstructured":"Apache Giraph . http:\/\/giraph.apache.org\/ , 2017 . Apache Giraph. http:\/\/giraph.apache.org\/, 2017."},{"key":"e_1_2_1_2_1","volume-title":"http:\/\/webdatacommons.org\/hyperlinkgraph\/2012-08\/","author":"Common Crawl","year":"2017","unstructured":"Common Crawl 2012 Host graph. http:\/\/webdatacommons.org\/hyperlinkgraph\/2012-08\/ , 2017 . Common Crawl 2012 Host graph. http:\/\/webdatacommons.org\/hyperlinkgraph\/2012-08\/, 2017."},{"key":"e_1_2_1_3_1","volume-title":"https:\/\/code.facebook.com\/posts\/319004238457019\/a-comparison-of-state-of-the-art-graph-processing-systems\/","author":"A","year":"2017","unstructured":"A comparison of state-of-the-art graph processing systems. https:\/\/code.facebook.com\/posts\/319004238457019\/a-comparison-of-state-of-the-art-graph-processing-systems\/ , 2017 . A comparison of state-of-the-art graph processing systems. https:\/\/code.facebook.com\/posts\/319004238457019\/a-comparison-of-state-of-the-art-graph-processing-systems\/, 2017."},{"key":"e_1_2_1_4_1","volume-title":"http:\/\/graph500.org\/","year":"2017","unstructured":"Graph500. http:\/\/graph500.org\/ , 2017 . Graph500. http:\/\/graph500.org\/, 2017."},{"key":"e_1_2_1_5_1","volume-title":"https:\/\/snap.stanford.edu\/data\/soc-LiveJournal1.html","author":"LiveJournal","year":"2017","unstructured":"LiveJournal graph. https:\/\/snap.stanford.edu\/data\/soc-LiveJournal1.html , 2017 . LiveJournal graph. https:\/\/snap.stanford.edu\/data\/soc-LiveJournal1.html, 2017."},{"key":"e_1_2_1_6_1","volume-title":"http:\/\/www.openmp.org\/","author":"MP.","year":"2017","unstructured":"Open MP. http:\/\/www.openmp.org\/ , 2017 . OpenMP. http:\/\/www.openmp.org\/, 2017."},{"key":"e_1_2_1_7_1","volume-title":"http:\/\/law.di.unimi.it\/webdata\/twitter-2010\/","author":"Twitter","year":"2017","unstructured":"Twitter graph. http:\/\/law.di.unimi.it\/webdata\/twitter-2010\/ , 2017 . Twitter graph. http:\/\/law.di.unimi.it\/webdata\/twitter-2010\/, 2017."},{"key":"e_1_2_1_8_1","volume-title":"http:\/\/networkrepository.com\/web-uk-2005-all.php","year":"2017","unstructured":"UK-2005 graph. http:\/\/networkrepository.com\/web-uk-2005-all.php , 2017 . UK-2005 graph. http:\/\/networkrepository.com\/web-uk-2005-all.php, 2017."},{"key":"e_1_2_1_9_1","volume-title":"http:\/\/networkrepository.com\/soc-sinaweibo.php","author":"Weibo","year":"2017","unstructured":"Weibo graph. http:\/\/networkrepository.com\/soc-sinaweibo.php , 2017 . Weibo graph. http:\/\/networkrepository.com\/soc-sinaweibo.php, 2017."},{"key":"e_1_2_1_10_1","volume-title":"https:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/Gleich\/wikipedia-20070206.html","author":"Wikipedia","year":"2017","unstructured":"Wikipedia graph. https:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/Gleich\/wikipedia-20070206.html , 2017 . Wikipedia graph. https:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/Gleich\/wikipedia-20070206.html, 2017."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.86"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342011403516"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741970"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2621934.2621936"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04898-2_498"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1085"},{"key":"e_1_2_1_19_1","first-page":"17","volume-title":"10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012","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 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012 , Hollywood, CA, USA, October 8--10 , 2012 , 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 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8--10, 2012, pages 17--30, 2012."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2808797.2809333"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0305-0"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2016.7761646"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2039367"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465369"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3014904.3014999"},{"key":"e_1_2_1_26_1","first-page":"31","volume-title":"10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012","author":"Kyrola A.","year":"2012","unstructured":"A. Kyrola , G. E. Blelloch , and C. Guestrin . GraphChi: Large-scale graph computation on just a PC . In 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012 , Hollywood, CA, USA, October 8--10 , 2012 , pages 31 -- 46 , 2012. A. Kyrola, G. E. Blelloch, and C. Guestrin. GraphChi: Large-scale graph computation on just a PC. In 10th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2012, Hollywood, CA, USA, October 8--10, 2012, pages 31--46, 2012."},{"key":"e_1_2_1_27_1","first-page":"340","volume-title":"UAI 2010, Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence","author":"Low Y.","year":"2010","unstructured":"Y. Low , J. Gonzalez , A. Kyrola , D. Bickson , C. Guestrin , and J. M. Hellerstein . GraphLab: A new framework for parallel machine learning . In UAI 2010, Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence , Catalina Island, CA, USA, July 8--11 , 2010 , pages 340 -- 349 , 2010. Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. GraphLab: A new framework for parallel machine learning. In UAI 2010, Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, Catalina Island, CA, USA, July 8--11, 2010, pages 340--349, 2010."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064191"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815408"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610518"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556572"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809983"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465371"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484427"},{"key":"e_1_2_1_41_1","first-page":"15","volume-title":"Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2012","author":"Zaharia M.","year":"2012","unstructured":"M. Zaharia , M. Chowdhury , T. Das , A. Dave , J. Ma , M. McCauly , M. J. Franklin , S. Shenker , and I. Stoica . Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing . In Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2012 , San Jose, CA, USA, April 25--27 , 2012 , pages 15 -- 28 , 2012. M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauly, M. J. Franklin, S. Shenker, and I. Stoica. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2012, San Jose, CA, USA, April 25--27, 2012, pages 15--28, 2012."},{"key":"e_1_2_1_42_1","first-page":"301","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016","author":"Zhu X.","year":"2016","unstructured":"X. Zhu , W. Chen , W. Zheng , and X. Ma . Gemini: A computation-centric distributed graph processing system . In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016 , Savannah, GA, USA, November 2--4 , 2016 ., pages 301 -- 316 , 2016. X. Zhu, W. Chen, W. Zheng, and X. Ma. Gemini: A computation-centric distributed graph processing system. In 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2--4, 2016., 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\/3204028.3204035","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:21:48Z","timestamp":1672222908000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3204028.3204035"}},"subtitle":["a scalable link- and locality-aware linear algebra-based graph analytics system"],"short-title":[],"issued":{"date-parts":[[2018,4]]},"references-count":42,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["10.14778\/3204028.3204035"],"URL":"https:\/\/doi.org\/10.14778\/3204028.3204035","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,4]]}}}