Accelerating Maximal Bicliques Enumeration with GPU on large scale network
Article
Wu, Chunqi, Li, Jingdong, Li, Zhao, Zhang, Ji and Tang, Pan. 2024. "Accelerating Maximal Bicliques Enumeration with GPU on large scale network." Future Generation Computer Systems: the international journal of grid computing: theory, methods and applications. 161, pp. 601-613. https://doi.org/10.1016/j.future.2024.07.021
Article Title | Accelerating Maximal Bicliques Enumeration with GPU on large scale network |
---|---|
ERA Journal ID | 17858 |
Article Category | Article |
Authors | Wu, Chunqi, Li, Jingdong, Li, Zhao, Zhang, Ji and Tang, Pan |
Journal Title | Future Generation Computer Systems: the international journal of grid computing: theory, methods and applications |
Journal Citation | 161, pp. 601-613 |
Number of Pages | 13 |
Year | 2024 |
Publisher | Elsevier |
Place of Publication | Netherlands |
ISSN | 0167-739X |
1872-7115 | |
Digital Object Identifier (DOI) | https://doi.org/10.1016/j.future.2024.07.021 |
Web Address (URL) | https://www.sciencedirect.com/science/article/abs/pii/S0167739X2400387X |
Abstract | Bicliques, as a prevalent graph pattern, are of particular interest in graph mining and social network analysis, especially for detecting illegal activities on e-commerce platforms due to their dense structure. Overcoming the challenge of efficiently identifying all bicliques in large-scale graphs, called the Maximal Biclique Enumeration (MBE) problem, demands considerable computational power and remains a complex problem. The current MBE algorithms executed on CPUs, particularly their slow computation speeds on dealing with large-scale graphs, lack a more efficient alternative solution. Although GPUs are at least an order of magnitude faster than CPUs, the current MBE algorithm's framework cannot be optimized by the parallel computing architecture on GPUs. In this study, we introduce a novel framework, GPU-Accelerated Maximal Bicliques Enumeration (GMBE), which effectively utilizes the parallel processing capabilities of GPUs to accelerate the MBE algorithm. The GMBE propose an innovative, optimized biclique storage structure called the Compressed Bitmap Block (CBB), which supports both instruction-level and task-level parallelism. Additionally, we have developed a Application Programming Interface (API) aimed at accommodating the diverse requirements of data analysts, positioning GMBE as a middleware solution for graph mining applications in large-scale graph. Our experimental evaluation, conducted on a variety of real-world datasets, demonstrates that GMBE significantly outperforms current state-of-the-art MBE algorithms, with a significant speedup about 12X. GMBE sets as the initial GPU framework to solve the MBE problem in real-world datasets, successfully handling the millions of data, compared to previous studies. |
Keywords | Compressed Bitmap Block; Graph pattern mining; GPU acceleration; Large-scale graph; Maximal Biclique Enumeration |
Contains Sensitive Content | Does not contain sensitive content |
ANZSRC Field of Research 2020 | 461299. Software engineering not elsewhere classified |
Public Notes | Files associated with this item cannot be displayed due to copyright restrictions. |
Byline Affiliations | Southeast University, China |
Hangzhou Yugu Technology, China | |
East China Normal University, China | |
University of Southern Queensland |
Permalink -
https://research.usq.edu.au/item/z9968/accelerating-maximal-bicliques-enumeration-with-gpu-on-large-scale-network
21
total views0
total downloads2
views this month0
downloads this month