Multipredicate Join Algorithms for Accelerating Relational Graph Processing on GPUs
Haicheng Wu, Daniel Zinn, Molham Aref, Sudhakar Yalamanchili · Very Large Data Bases · 2014
Recent work has demonstrated that the use of programmable GPUs can be advantageous during relational query processing on analytical workloads. In this paper, we take a closer look at graph problems such as finding all triangles and all four-cliques of a graph. In particular, we present two different join algorithms for the GPU. The first is an implementation of Leapfrog-Triejoin (LFTJ), a recently presented worst-case optimal multi-predicate join algorithm. The second is a novel approach, inspired by the former but more suitable for GPU architectures. Our preliminary performance benchmarks show that for both approaches using GPUs is cost-effective. (the GPU implementation outperforms respective CPU variants). While the second algorithm is faster overall, it comes with increased implementation complexity and storage requirements for intermediary results. Furthermore, both our algorithms are competitive with the hand-written C++ implementation for finding triangles and four-cliques in the graph-processing system GraphLab executing on a multi-core CPU.