High Performance Exact Triangle Counting on GPUs
Authors:
- 3 August 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 28 (12) , 3501-3510
Abstract
This paper presents a GPU implementation of the graph triangle counting operation based on the set intersection algorithm. The algorithm is implemented in four kernels optimized for different types of graphs in a code delivering performance higher than the current state-of-the-art and without preprocessing the input graph. At runtime, a lightweight heuristic is used to select the kernel to run based on the specific graph taken as input. In contrast to previous works, the presented approach takes advantage of a set intersection operation implemented via bitmaps. Moreover, the simplicity of the approach allows the code to have limited size and engineering complexity.Keywords
This publication has 10 references indexed in Scilit:
- A Comparative Study on Exact Triangle Counting Algorithms on the GPU2016
- Counting Triangles in Large Graphs on GPU2016
- A Factored Sparse Approximate Inverse Preconditioned Conjugate Gradient Solver on Graphics Processing UnitsSIAM Journal on Scientific Computing, 2016
- Parallel Distributed Breadth First Search on the Kepler ArchitectureIEEE Transactions on Parallel and Distributed Systems, 2015
- Parallel Triangle Counting and Enumeration Using Matrix Algebra2015
- A Space-Efficient Streaming Algorithm for Estimating Transitivity and Triangle Counts Using the Birthday ParadoxACM Transactions on Knowledge Discovery From Data, 2015
- Wedge sampling for computing clustering coefficients and triangle counts on large graphs†Statistical Analysis and Data Mining: An ASA Data Science Journal, 2014
- The university of Florida sparse matrix collectionACM Transactions on Mathematical Software, 2011
- What is Twitter, a social network or a news media?2010
- Graph Twiddling in a MapReduce WorldComputing in Science & Engineering, 2009