Accelerating k-Core Decomposition on a GPU

Ahmad A., Yuan L., Yan D., Guo G., Chen J., Zhang C.

International Conference on Data Engineering, California, Amerika Birleşik Devletleri, 3 - 07 Nisan 2023, ss.1-12

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Basıldığı Şehir: California
  • Basıldığı Ülke: Amerika Birleşik Devletleri
  • Sayfa Sayıları: ss.1-12
  • TED Üniversitesi Adresli: Evet

Özet

The k-core of a graph is the largest induced

subgraph with minimum degree k. The problem of k-core

decomposition finds the k-cores of a graph for all valid values

of k, and it has many applications such as network analysis,

computational biology and graph visualization. Currently, there

are two types of parallel algorithms for k-core decomposition on

a big graph: (1) degree-based vertex peeling, and (2) iterative h-

index refinement. There is, however, few studies on accelerating

k-core decomposition using GPU. In this paper, we propose

a highly optimized peeling algorithm on a GPU for k-core

decomposition, and compare it with possible implementations

on top of think-like-a-vertex graph-parallel GPU systems as well

as existing serial and parallel k-core decomposition algorithms

on CPUs. Extensive experiments show that our GPU algorithm

is the overall winner in both time and space.