Page 76 - 《软件学报》2026年第3期

李忠根 等: GPU 加速的高维向量聚类算法 1039

间的距离计算; 其次, 为了高效地划分大规模数据, 设计了层间并行计算模式, 利用 GPU 中的 Tensor 核心加速 K-means
树的计算, 使得 GPU 能够对每一层的树节点进行并行计算, 避免了数据点规模的指数衰减对并行计算效率产生的
影响; 最后, 基于 K 近邻图索引进行并行广度优先遍历, 加速分区局部 DBSCAN 计算, 利用不同分区的核心点之
间的密度直达关系构建核心近邻图, 基于核心近邻图合并局部计算结果, 减少了遍历所有数据点带来的计算开销.
本文的主要贡献总结为以下 4 点.
(1) 设计了一种 GPU 加速的 K 近邻图构建算法. 该算法利用 GPU 和偏好采样策略协同加速向量间距离计算
与近邻更新, 显著提高了计算效率.
(2) 设计了一种 Tensor 核心增强的层间并行 K-means 树分区算法. 层间并行计算模式避免了数据点规模的指
数衰减对并行计算产生的影响, 保证在生成 K-means 树的过程中对 GPU 资源的充分利用.
(3) 提出了基于广度优先遍历策略和核心近邻图的高效并行聚类方法. 并行广度优先遍历显著加速了分区局
部 DBSCAN 计算. 同时, 核心近邻图减少了遍历所有数据点带来的计算开销, 极大地提升了聚类效率.
(4) 在 4 个真实数据集上开展了详尽的实验评估, 与现有方法进行了对比. 结果表明, 相比于现有的基于树索
引和图索引及 GPU 加速的方法, 本文提出的方法在保证精度的同时, 显著提升了高维向量聚类的计算效率.
本文第 1 节介绍基于近邻图和 GPU 加速的 DBSCAN 的相关工作与研究现状. 第 2 节介绍 DBSCAN 算法及
基于 K 近邻图的 DBSCAN 算法的相关基础知识. 第 3 节介绍 GPU 加速的高维向量聚类算法. 第 4 节进行实验分
析, 验证并分析算法的性能. 第 5 节总结全文.

1 相关工作

本节总结与本文相关的研究工作, 第 1.1 节介绍基于近邻图的 DBSCAN 的相关工作, 第 1.2 节总结 GPU 加速
的 DBSCAN 的相关工作.
1.1 基于近邻图的 DBSCAN 算法
Gan 等人 [32] 指出, 当数据维度大于 3 时, DBSCAN 的计算开销将显著增加, 这使得高维场景下的近似 DBSCAN
算法设计成为必然选择. 为了加速 DBSCAN 中开销最高的近邻查询, 现有研究使用多种数据结构优化近邻查询, 例
如局部敏感哈希 (locality sensitive hashing, LSH) [33,34] 、KD 树 [15,16] 、覆盖树 [35] 等. 然而在高维场景下, 基于哈希或
树等数据结构的方法将面临维度灾难, 且存在效率低下的问题. 为了进一步加速高维空间向量聚类计算, PARDICLE [36]
构建了 ε 近邻图, 并设计了一种密度估计方法, 在密集区域采样计算最近邻, 而在稀疏区域执行精确最近邻, 以降
低 DBSCAN 的计算量. NG-DBSCAN [21] 提出了一种快速构建 ε 近邻图的方法, 即随机初始化图中节点的近邻, 每
ε, 并根据判断结果更新节点的邻居列表, 直至达到既定迭代次
次迭代时判断节点及其二阶邻居的距离是否小于
数. 为了进一步减小 ε 近邻图的构造代价, SNG-DBSCAN [37] 提出一种采样方法, 基于该方法构造了 ε 近邻图. KNN-
DBSCAN [22] 指出, 上述基于 ε 近邻图的方法在高维场景下对 ε 的取值十分敏感, ε 取值发生变动时即需重新构建近
邻图结构, 而这将产生极高的索引构建开销. 为此, h-DBSCAN [19,20] 使用 HNSW 图 [38] 作为索引, 基于该索引进行高
效的近邻查询以加速 DBSCAN 算法. 为了避免额外的索引查询开销, KNN-DBSCAN [22] 使用 K 近邻图作为索引结
构, 引入了新的核心点、可达等 DBSCAN 相关概念的定义方式, 重新定义了基于密度的聚类, 基于最小生成树计
算聚类. 然而, 这类方法在高维场景下仍面临索引构建低效的问题, 制约了聚类效率的提升.
1.2 GPU 加速的 DBSCAN 算法
CPU 架构受限于有限运算能力, 难以满足高效 DBSCAN 计算的需求. 由于 DBSCAN 的开销主要来源于近邻
点搜索, 其中涉及大量的距离计算, 这促使研究者转向利用 GPU 的并行架构寻求加速. 现有的 GPU 加速 DBSCAN
的算法分为 3 类: 全局聚类计算、分区聚类计算和基于索引的聚类计算. 全局聚类计算利用 GPU 强大的计算能力
遍历数据集为各数据点计算近邻点, 如 CUDA-DClust [39] 和 Cal-DBSCAN [40] 将每个数据点划分至不同的线程并行
计算近邻点; G-DBSCAN [41] 则遍历所有数据点以构造密度连通图, 而后在该近邻图上开展并行广度优先搜索, 以
扩展簇的范围. 上述方法对所有数据点的遍历造成了大量的计算开销. 分区聚类计算首先将数据进行分区, 将近邻