GPU并行加速Gabriel图构建：提速最高8484倍
原始标题 / GPU-Accelerated Construction of the Gabriel Graph: Parallelization Strategies and Applications to Large-Margin Classification and Graph-Based Clustering
提出CUDA并行策略，消除显式邻接结构、按边压缩存储并引入线程粗化，将Gabriel图构建时间较CPU基线降低2至近4个数量级；在14个公开数据集上分类精度不降，并支撑一种无需密度半径参数的聚类方法。
01 摘要
事实：论文提出三种CUDA策略（线性线程索引隐式映射顶点对、两遍位掩码原子压缩边表、线程粗化）加速Gabriel图构建。事实：在14个公开基准上，GPU实现较顺序CPU基线加速最高8484倍且分类精度无损；所提聚类方法在Dunn指数上与DBSCAN统计竞争且无需显式密度半径。作者观点：这些策略使Gabriel图在更大规模数据上实用化，并拓展至密度感知聚类。
02 关键点
- 隐式闭式映射将线性线程索引直接对应顶点对(i,j)，无需O(N²)邻接结构，实现常数时间和常数内存定位。
- 两遍位掩码原子压缩边表仅生成与实际边数成比例的稠密边数组。
- 线程粗化让每线程评估多个候选对，权衡启动调度开销与负载均衡。
回到一手来源
阅读原文 ↗AI GENERATED SUMMARY / DISCOVERED BY ARXIV CS.LG