Name
Abstract | ||
|---|---|---|
The GraphBLAS standard defines a set of fundamental building blocks for formulating graph algorithms in the language of linear algebra. Since its first release in 2017, the expressivity of the GraphBLAS API and the performance of its implementations (such as SuiteSparse: GraphBLAS) have been studied on a number of textbook graph algorithms such as BFS, single-source shortest path, and connected components. However, less attention was devoted to other aspects of graph processing such as handling typed and attributed graphs (also known as property graphs), and making use of complex graph query techniques (handling paths, aggregation, and filtering). To study these problems in more detail, we have used GraphBLAS to solve the case study of the 2014 SIGMOD Programming Contest, which defines complex graph processing tasks that require a diverse set of operations. Our solution makes heavy use of multi-source BFS algorithms expressed as sparse matrix-matrix multiplications along with other GraphBLAS techniques such as masking and submatrix extraction. While the queries can be formulated in GraphBLAS concisely, our performance evaluation shows mixed results. For some queries and data sets, the performance is competitive with the hand-optimized top solutions submitted to the contest, however, in some cases, it is currently outperformed by orders of magnitude. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1109/HPEC43674.2020.9286186 | 2020 IEEE High Performance Extreme Computing Conference (HPEC) |
Keywords | DocType | ISSN |
breadth-first search,submatrix extraction,masking,GraphBLAS techniques,sparse matrix-matrix multiplications,multisource BFS algorithms,complex graph processing tasks,complex graph query techniques,property graphs,textbook graph algorithms,GraphBLAS API,linear algebra,GraphBLAS standard,SIGMOD 2014 Programming Contest | Conference | 2377-6943 |
ISBN | Citations | PageRank |
978-1-7281-9220-8 | 0 | 0.34 |
References | Authors | |
14 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Márton Elekes | 1 | 0 | 0.68 |
| Attila Nagy | 2 | 0 | 0.34 |
| Dávid Sándor | 3 | 0 | 0.34 |
| János Benjamin Antal | 4 | 1 | 1.02 |
| TIMOTHY A. DAVIS | 5 | 1447 | 144.19 |
| Gábor Szárnyas | 6 | 0 | 0.34 |