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

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

有效性, 并与基线算法对应模块及同类方法进行对比.
4.6.1 近邻图索引构建
本节使用表 1 中的两个代表性数据集 DEEP1M 和 SIFT1M 及其各自的默认参数, 对 5 种近邻图索引构建方
法进行评估. 其中, KNN-DBSCAN 使用开源库 GOFMM [55] 中的随机投影树构建 K 近邻图, h-DBSCAN 使用开源
库 HNSWlib [56] 构建 HNSW 图索引, KGraph [57] 、cuVS [58] 和本文所提出的 KG-DBSCAN 均使用 NN-Descent 构建
K 近邻图, 不同的是, KGraph 在 CPU 上运行、cuVS 使用 GPU 加速距离计算并使用 CPU 进行邻居更新、KG-
DBSCAN 进一步改进了 NN-Descent 算法并使用 GPU 进行全流程加速. 5 种近邻图索引构建的运行时间如图 9 所
示, KG-DBSCAN 在两个数据集上的近邻图索引构建平均效率相比于 KNN-DBSCAN、h-DBSCAN、KGraph 和
cuVS 分别快 25.2 倍、23.4 倍、14.2 倍和 3.4 倍, 实现了高效的近邻图索引构建. 这是由于 KG-DBSCAN 充分利
用了 GPU 的高并发特性, 基于其特性优化距离计算与邻居更新操作, 并将各数据点的计算解耦, 避免了同步开销.
相比于 cuVS, KG-DBSCAN 将计算全流程卸载至 GPU, 避免了 CPU 与 GPU 之间频繁的数据传输和同步带来的
额外开销, 进一步提高了近邻图索引的构建效率.

A (KNN-DBSCAN) B (h-DBSCAN) C (KGraph) D (cuVS) E (KG-DBSCAN)
150 150

运行时间 (s) 100 运行时间 (s) 100

50
50

0 0
A B C D E A B C D E
(a) DEEP1M 数据集 (b) SIFT1M 数据集
图 9 近邻图索引构建时间对比

此外, 本节在两个代表性数据集上将近邻图度数 k 对聚类精度的影响进行了评估, k 在 [minPts,3×minPts] 区
间范围内均匀取 5 个值, 并固定 K 近邻图构造算法的迭代次数. 实验结果如图 10 所示.

F1 分数 运行时间 F1 分数 运行时间
10 1.00 7 1.00
6 0.98
0.98
运行时间 (s) F1 分数 运行时间 (s) 5 F1 分数
8
6
0.96
4 0.96
4 0.94 3 0.94
1.0 1.5 2.0 2.5 3.0 1.0 1.5 2.0 2.5 3.0
k (×minPts) k (×minPts)
(a) DEEP1M 数据集 (b) SIFT1M 数据集
图 10 K 近邻图度数对聚类精度的影响

聚类算法的运行时间随 K 近邻图度数的增加而增加. 这是因为 K 近邻图的构建具有较高的计算复杂度, 其运
行时间占据了聚类算法 80% 以上的开销, K 近邻图度数的增加将导致 K 近邻图构造算法的开销增加. 此外, 在两
个数据集上都可以观察到, 随着近邻图度数的增加, F1 分数呈先增后减的趋势. 这是由于当 k 小于等于 2×minPts
时, 近邻图度数的增加使得各数据点的 ε 邻域内的点更精确, 而当 k 超过 2×minPts 时, 由于各数据点的近邻数量增