GPU 加速构建 Gabriel 图：并行化策略及其在大间隔分类与图聚类中的应用
GPU-Accelerated Construction of the Gabriel Graph: Parallelization Strategies and Applications to Large-Margin Classification and Graph-Based Clustering
Diego Sanches Nere dos Santos · Luiz Carlos Bambirra Torres
中文摘要
Gabriel 图是一种邻近图(proximity graph)，广泛用于计算几何与几何机器学习，是大间隔分类器的基础；研究还表明，它可用于密度感知聚类。朴素构建的时间复杂度为 O(N^3)，严重限制了其在数千个以上样本数据集上的应用。论文给出基于 CUDA 的一组 GPU 并行化策略：建立从线性线程索引到顶点对 (i,j) 的隐式闭式映射，无需显式 O(N^2) 邻接结构，使每个线程以常数时间和内存定位顶点对；采用两阶段、基于位掩码和原子压缩的边列表构建，仅按实际找到的边生成稠密边数组；通过线程粗化(thread coarsening)让每个线程计算多个候选顶点对，在启动与调度开销和负载均衡之间取得平衡。策略用于加速基于 Gabriel 图的大间隔分类器 NN-clas，以及一种新聚类算法；后者在残差图中识别连通分量，并执行 GPU 并行 Union-Find 和分层边合并。在 14 个公开 benchmark 数据集上，GPU 构建时间较顺序 CPU 基线降低 2 至近 4 个数量级，最高加速 8484x，且分类精度无损；在拓扑有效性指标 Dunn 上，该聚类方法与 DBSCAN 具有统计竞争力，同时无需显式密度半径参数。
关键要点
- 01朴素 Gabriel 图构建复杂度为 O(N^3)，难以扩展到数千样本以上。
- 02隐式顶点对映射以常数时间和内存移除 O(N^2) 邻接结构需求。
- 03两阶段位掩码与原子压缩边列表，仅按实际边数生成稠密数组。
- 04线程粗化在启动、调度开销与负载均衡之间进行权衡。
- 05GPU 构建最高加速 8484x，分类精度无损，聚类无需密度半径参数。
解读
尚无解读。
原始英文摘要
arXiv:2610.28759v1 Announce Type: cross Abstract: The Gabriel graph is a proximity graph widely used in computational geometry and geometric machine learning, underlying large-margin classifiers and, as we show in this work, density-aware clustering methods. Its construction, however, has cubic time complexity $O(N^3)$ in the naive formulation, which severely limits its use on datasets beyond a few thousand samples. This paper presents a set of GPU parallelization strategies, implemented in CUDA, that make Gabriel graph construction practical at scale. We introduce (i) an implicit closed-form mapping from a linear thread index to the corresponding vertex pair $(i,j)$, which removes the need for an explicit $O(N^2)$ adjacency structure and lets every thread locate its pair in constant time and constant memory; (ii) a two-pass, bitmask-based, atomically-compacted edge-list construction that produces a dense edge array proportional only to the number of edges actually found; and (iii) a thread-coarsening strategy in which each thread evaluates several candidate pairs, trading launch and scheduling overhead against load balance. We evaluate these strategies on the acceleration of a Gabriel-graph-based large-margin classifier (NN-clas) and on a novel Gabriel-graph clustering algorithm that identifies connected components on a residual graph and performs GPU-parallel Union-Find with hierarchical edge-based merging. On 14 public benchmark datasets, the GPU implementation reduces Gabriel graph construction time by two to nearly four orders of magnitude relative to a sequential CPU baseline (up to 8484x), without loss of classification accuracy, and the proposed clustering method is statistically competitive with DBSCAN on the topological validity index Dunn while eliminating the need for an explicit density radius parameter.