Skip to main content
eScholarship
Open Access Publications from the University of California

A Comparative Study on Exact Triangle Counting Algorithms on the GPU

  • Author(s): Wang, Leyuan
  • Wang, Yangzihao
  • Yang, Carl
  • Owens, John D
  • et al.
Abstract

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's open access policies. Let us know how this access is important for you.

Main Content
Current View