Accelerating k-Core Decomposition by a GPU

Akhlaque Ahmad, Lyuheng Yuan, Da Yan, Guimu Guo, Jieyang Chen, Chengcui Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


The k-core of a graph is the largest induced sub-graph 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: (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, 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. Our source code is released at

Original languageEnglish (US)
Title of host publicationProceedings - 2023 IEEE 39th International Conference on Data Engineering, ICDE 2023
PublisherIEEE Computer Society
Number of pages14
ISBN (Electronic)9798350322279
StatePublished - 2023
Event39th IEEE International Conference on Data Engineering, ICDE 2023 - Anaheim, United States
Duration: Apr 3 2023Apr 7 2023

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Conference39th IEEE International Conference on Data Engineering, ICDE 2023
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'Accelerating k-Core Decomposition by a GPU'. Together they form a unique fingerprint.

Cite this