Name
Abstract | ||
|---|---|---|
The rise of graph analytic systems has created a need for new ways to measure and compare the capabilities of graph processing systems. The MIT/Amazon/IEEE Graph Challenge has been developed to provide a well-defined community venue for stimulating research and highlighting innovations in graph analysis software, hardware, algorithms, and systems. GraphChallenge.org provides a wide range of pre-parsed graph data sets, graph generators, mathematically defined graph algorithms, example serial implementations in a variety of languages, and specific metrics for measuring performance. The triangle counting component of GraphChallenge.org tests the performance of graph processing systems to count all the triangles in a graph and exercises key graph operations found in many graph algorithms. In 2017, 2018, and 2019 many triangle counting submissions were received from a wide range of authors and organizations. This paper presents a performance analysis of the best performers of these submissions. These submissions show that their state-of-the-art triangle counting execution time, T
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">tri</sub>
, is a strong function of the number of edges in the graph, Ne, which improved significantly from 2017 (T
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">tri</sub>
≈ (N
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">e</sub>
/10
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">8</sup>
)
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4/3</sup>
) to 2018 (T
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">tri</sub>
≈ N
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">e</sub>
/10
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">9</sup>
) and remained comparable from 2018 to 2019. Graph Challenge provides a clear picture of current graph analysis systems and underscores the need for new innovations to achieve high performance on very large graphs. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1109/HPEC43674.2020.9286166 | 2020 IEEE High Performance Extreme Computing Conference (HPEC) |
Keywords | DocType | ISSN |
GraphChallenge.org triangle counting performance,graph processing systems,graph analysis software,pre-parsed graph data sets,graph generators,triangle counting component,performance analysis,key graph operations | Conference | 2377-6943 |
ISBN | Citations | PageRank |
978-1-7281-9220-8 | 2 | 0.37 |
References | Authors | |
80 | 12 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Siddharth Samsi | 1 | 201 | 24.09 |
| Kepner Jeremy | 2 | 2 | 0.37 |
| Vijay Gadepally | 3 | 449 | 50.53 |
| Hurley Michael | 4 | 2 | 0.37 |
| Michael J. Jones | 5 | 11341 | 927.21 |
| Edward K. Kao | 6 | 123 | 10.06 |
| Sanjeev Mohindra | 7 | 76 | 5.38 |
| Albert Reuther | 8 | 335 | 37.32 |
| Steven Smith | 9 | 75 | 4.23 |
| Song William | 10 | 2 | 0.37 |
| Diane Staheli | 11 | 104 | 8.96 |
| Monticciolo Paul | 12 | 2 | 0.37 |