arXiv cs.AI· Diego Sanches Nere dos Santos, Luiz Carlos Bambirra Torres·· 12 小时前AI 评分26
GPU 加速 Gabriel 图构建：面向大间隔分类与图聚类的 CUDA 并行化策略
GPU-Accelerated Construction of the Gabriel Graph: Parallelization Strategies and Applications to Large-Margin Classification and Graph-Based Clustering
AI 导读
该论文提出一套 CUDA 并行化策略，将 Gabriel 图构建时间相比串行 CPU 基线缩短 2 至近 4 个数量级（最高 8484x），且不损失分类精度。核心方法包括线性线程索引到顶点对 (i,j) 的隐式闭式映射、基于位掩码与原子压缩的两遍边表构建，以及线程粗化策略。
正文 · AI 翻译
摘要：Gabriel 图是一种邻近图，广泛应用于计算几何和几何机器学习，是大幅量分类器的基础，并且如本文所示，也是密度感知聚类方法的基础。然而，其构建在朴素形式下具有三次时间复杂度 $O(N^3)$，这严重限制了它在超过几千个样本的数据集上的使用。本文提出了一套在 CUDA 中实现的 GPU 并行化策略，使 Gabriel 图构建在大规模下变得实用。我们引入了：(i) 一种从线性线程索引到对应顶点对 $(i,j)$ 的隐式闭式映射，它消除了对显式 $O(N^2)$ 邻接结构的需求，并让每个线程在常数时间和常数内存内定位其配对；(ii) 一种两遍、基于位掩码、原子压缩的边列表构建方法，它生成一个仅与实际找到的边数成正比的稠密边数组；(iii) 一种线程粗化策略，其中每个线程评估多个候选对，在启动和调度开销与负载均衡之间进行权衡。我们在基于 Gabriel 图的大幅量分类器（NN-clas）的加速上，以及一种新颖的 Gabriel 图聚类算法上评估了这些策略；该算法在残差图上识别连通分量，并执行带基于层次边合并的 GPU 并行 Union-Find。在 14 个公开基准数据集上，相对于顺序 CPU 基线，GPU 实现将 Gabriel 图构建时间缩短了两个到近四个数量级（最高达 8484 倍），且不损失分类准确率；所提出的聚类方法在拓扑有效性指数 Dunn 上与 DBSCAN 具有统计竞争力，同时消除了对显式密度半径参数的需求。
| 评论： | 12 页，3 幅图，1 张表 |
| 主题： | 分布式、并行与集群计算 (cs.DC)；人工智能 (cs.AI)；机器学习 (cs.LG) |
| 引用为： | arXiv:2610.28759 [cs.DC] |
| （或 arXiv:2610.28759v1 [cs.DC] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.28759 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Diego Sanches Nere Dos Santos [查看电子邮件]
[v1]
2026 年 10 月 20 日星期二 18:03:08 UTC（39 KB）
来源：arXiv cs.AI · arxiv.org