A Comparative Study on Exact Triangle Counting Algorithms on the GPU
- Author(s): Wang, Leyuan
- Wang, Yangzihao
- Yang, Carl
- Owens, John D
- et al.
Published Web Locationhttps://doi.org/10.1145/2915516.2915521
We implement exact triangle counting in graphs on the GPU using three different methodologies: subgraph matching to a triangle pattern; programmable graph analytics, with a set-intersection approach; and a matrix formulation based on sparse matrix-matrix multiplies. All three deliver best-of-class performance over CPU implementations and over comparable GPU implementations, with the graph-analytic approach achieving the best performance due to its ability to exploit efficient filtering steps to remove unnecessary work and its high-performance set-intersection core.
Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.