Incremental Connected Component Detection for Graph Streams on GPU
Studies on the real-time detection of connected components in graph streams have been carried out. The existing connected component detection method cannot process connected components incrementally, and the performance deteriorates due to frequent data transmission when GPU is used. In this paper,...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-03-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/12/6/1465 |
| _version_ | 1797612206264680448 |
|---|---|
| author | Kyoungsoo Bok Namyoung Kim Dojin Choi Jongtae Lim Jaesoo Yoo |
| author_facet | Kyoungsoo Bok Namyoung Kim Dojin Choi Jongtae Lim Jaesoo Yoo |
| author_sort | Kyoungsoo Bok |
| collection | DOAJ |
| description | Studies on the real-time detection of connected components in graph streams have been carried out. The existing connected component detection method cannot process connected components incrementally, and the performance deteriorates due to frequent data transmission when GPU is used. In this paper, we propose a new incremental processing method to solve the problems found in the existing methods for detecting connected components on GPUs. The proposed method minimizes the amount of data to be sent to the GPU by determining the subgraph affected by the graph stream update and by detecting the part to be recalculated. We consider the number of vertices to quickly determine the connected components of a graph stream on the GPU. An asynchronous execution method is used to shorten the transfer time between the CPU and the GPU according to real-time graph stream changes. In order to show that the proposed method provides fast incremental connected component detection on the GPU, we evaluated its performance using various datasets. |
| first_indexed | 2024-03-11T06:37:59Z |
| format | Article |
| id | doaj.art-9fd4b2fbeec640c08e4bfe7ffa3d946c |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-11T06:37:59Z |
| publishDate | 2023-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-9fd4b2fbeec640c08e4bfe7ffa3d946c2023-11-17T10:45:55ZengMDPI AGElectronics2079-92922023-03-01126146510.3390/electronics12061465Incremental Connected Component Detection for Graph Streams on GPUKyoungsoo Bok0Namyoung Kim1Dojin Choi2Jongtae Lim3Jaesoo Yoo4Department of Artificial Intelligence Convergence, Wonkwang University, Iksandae 460, Iksan 54538, Jeonbuk, Republic of KoreaDepartment of Information and Communication Engineering, Chungbuk National University, Chungdae-ro 1, Seowon-gu, Cheongju 28644, Chungbuk, Republic of KoreaDepartment of Computer Engineering, Changwon National University, Changwondaehak-ro 20, Uichang-gu, Changwon 51140, Gyeongsangnam, Republic of KoreaDepartment of Information and Communication Engineering, Chungbuk National University, Chungdae-ro 1, Seowon-gu, Cheongju 28644, Chungbuk, Republic of KoreaDepartment of Information and Communication Engineering, Chungbuk National University, Chungdae-ro 1, Seowon-gu, Cheongju 28644, Chungbuk, Republic of KoreaStudies on the real-time detection of connected components in graph streams have been carried out. The existing connected component detection method cannot process connected components incrementally, and the performance deteriorates due to frequent data transmission when GPU is used. In this paper, we propose a new incremental processing method to solve the problems found in the existing methods for detecting connected components on GPUs. The proposed method minimizes the amount of data to be sent to the GPU by determining the subgraph affected by the graph stream update and by detecting the part to be recalculated. We consider the number of vertices to quickly determine the connected components of a graph stream on the GPU. An asynchronous execution method is used to shorten the transfer time between the CPU and the GPU according to real-time graph stream changes. In order to show that the proposed method provides fast incremental connected component detection on the GPU, we evaluated its performance using various datasets.https://www.mdpi.com/2079-9292/12/6/1465connected componentGPUgraph streamincremental processing |
| spellingShingle | Kyoungsoo Bok Namyoung Kim Dojin Choi Jongtae Lim Jaesoo Yoo Incremental Connected Component Detection for Graph Streams on GPU Electronics connected component GPU graph stream incremental processing |
| title | Incremental Connected Component Detection for Graph Streams on GPU |
| title_full | Incremental Connected Component Detection for Graph Streams on GPU |
| title_fullStr | Incremental Connected Component Detection for Graph Streams on GPU |
| title_full_unstemmed | Incremental Connected Component Detection for Graph Streams on GPU |
| title_short | Incremental Connected Component Detection for Graph Streams on GPU |
| title_sort | incremental connected component detection for graph streams on gpu |
| topic | connected component GPU graph stream incremental processing |
| url | https://www.mdpi.com/2079-9292/12/6/1465 |
| work_keys_str_mv | AT kyoungsoobok incrementalconnectedcomponentdetectionforgraphstreamsongpu AT namyoungkim incrementalconnectedcomponentdetectionforgraphstreamsongpu AT dojinchoi incrementalconnectedcomponentdetectionforgraphstreamsongpu AT jongtaelim incrementalconnectedcomponentdetectionforgraphstreamsongpu AT jaesooyoo incrementalconnectedcomponentdetectionforgraphstreamsongpu |