Show simple item record

AuthorAhmad Y.
AuthorKhattab O.
AuthorMalik A.
AuthorMusleh A.
AuthorHammoud M.
AuthorKutlu M.
AuthorShehata M.
AuthorElsayed T.
Available date2020-02-06T08:09:21Z
Publication Date2018
Publication NameProceedings of the VLDB Endowment
ISSN21508097
URIhttp://dx.doi.org/10.14778/3204028.3204035
URIhttp://hdl.handle.net/10576/12866
AbstractThis paper presents LA3, 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 super uous computations. We refer to this novel optimization as computation filtering. Second, a communication filtering 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 pseudo-asynchronous computation and communication 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 10�. - 2018 VLDB Endowment 21508097/18/4.
Languageen
PublisherAssociation for Computing Machinery
TitleLA3: A scalable link-and locality-aware linear algebra-based graph analytics system
TypeConference Paper
Pagination920-933
Issue Number8
Volume Number11


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record