.png){kind=icon}
返回
Efficient Bitruss Decomposition on GPU
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2025.3569804.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
在二分图上的凝聚子图计算近来已引起显著的研究兴趣。作为流行的凝聚子图模型，k-bitruss被定义为最大子图，其中每条边至少包含k个蝴蝶（即一个(2,2)-完全二分图）。bitruss分解问题已被广泛研究，其目标是为k≥0计算所有k-bitruss。当前基于CPU的最先进解决方案需要大量成本来构建用于分组蝴蝶的索引结构，导致在大型二分图上的可扩展性挑战。在本文中，我们通过利用GPU架构的并行计算能力来探索基于GPU的bitruss分解。由于基于索引的方法需要大量空间且GPU的内存资源有限，我们提出了GBiD，这是一种基于GPU的剥离算法，它利用以块为中心的计算方案，在不使用任何索引结构的情况下实现空间高效的bitruss分解。此外，提出了成本感知的公共邻居探索和邻居列表访问优化，以通过减少剥离过程中枚举蝴蝶和访问图结构的成本来增强GBiD。在10个真实数据集上进行的大量实验表明，我们提出的技术在空间和时间效率方面显著优于现有的基于CPU的解决方案。
Keyword:
Bipartite graph
cohesive subgraph
GPU
期刊
IF:
10.4
论文数:
6.8K
被引数:
3.2W
机构
引用论文
.png){kind=icon}
Efficient Sparse Matrix-Vector Multiplication on GPUs Using the CSR Storage FormatGpu上使用CSR存储格式的高效稀疏矩阵向量乘法
PREAI
分享收藏Scalable K-Core Decomposition for Static Graphs Using a Dynamic Graph Data Structure基于动态图数据结构的静态图可扩展K-核分解
PREAI
分享收藏分享收藏
查看更多内容