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

1038 软件学报 2026 年第 37 卷第 3 期

challenges in time efficiency and scalability. To address these issues, this study proposes a GPU-accelerated clustering algorithm for high-
dimensional vector data, introducing the K-nearest neighbor (KNN) graph index to accelerate DBSCAN. First, a GPU-accelerated parallel
KNN graph construction algorithm is developed, significantly reducing the index construction overhead. Furthermore, to enhance the
pipeline of DBSCAN and achieve highly concurrent vector clustering, a K-means tree partitioning algorithm with inter-layer parallelism
and a parallel clustering algorithm based on breadth-first search and a core KNN graph are designed. Finally, extensive experiments are
conducted on real-world datasets, and the proposed method is compared against existing approaches. Experimental results show that the
proposed algorithm improves the efficiency of large-scale vector clustering by 5.7–2 822.5 times while maintaining clustering accuracy.
Key words: density-based clustering; high-dimensional vector; GPU acceleration; parallel computing; K-nearest neighbor (KNN) graph

高维向量聚类是大规模向量数据分析的关键技术之一, 其通过将具有相似特征的向量划分至同一类别来揭示
数据分布的内在规律, 为异常检测、群体偏好识别和个性化推荐等数据分析任务提供技术支撑 [1] . 基于密度的空
[2]
间聚类算法 DBSCAN (density-based spatial clustering of applications with noise) 因其无须预先设定聚类数量、可
识别复杂簇结构及噪声点的优势, 已在自然语言处理 [3,4] 、图像处理 [5,6] 、音频分析 [7] 、生物数据分析 [8,9] 等领域获
得广泛应用. 随着人工智能与大数据技术的迅速发展, 文本、图像等数据向量化后的维度普遍达到数百维 [10] . 同
时, 向量数据集的数据规模亦普遍达到百万以上 [11] . 然而, DBSCAN 作为基于密度的聚类算法, 在面临大规模高维
向量时存在计算效率低下的问题, 难以满足实际应用场景中的高效聚类需求 [12] . 因此, 提高 DBSCAN 算法在面对
大规模高维向量时的计算效率成为亟待解决的重要课题.
DBSCAN 算法的计算开销主要来源于对每个数据对象的邻域计算 [13,14] . 为了降低计算代价, 现有的方法多采
用基于树或网格的索引加速 DBSCAN 的邻域计算 [15–18] . 然而, 基于树或网格的索引结构在处理高维向量数据时
易受维度灾难的影响, 导致近邻查询性能显著下降 [19,20] . 为了克服维度灾难带来的性能退化问题, 将近邻图结构
ε 近邻图 [21] 、K 近邻 (K-nearest neighbor, KNN) 图 [22] 、HNSW (hierarchical navigable small world graph,
(如
HNSW) [20] 等) 作为 DBSCAN 计算的索引结构已成为主流解决方案. 然而, 现有研究普遍基于 CPU 架构进行近邻
图构建以及 DBSCAN 聚类. 由于 CPU 少量核心导致的有限并行计算能力以及图索引构建较高的计算复杂度 [20–22] ,
使其难以满足大规模高维向量的高效聚类需求 [23] .
为了提升大规模向量数据的聚类效率, 研究者们开始利用 GPU 的强大并行能力加速 DBSCAN 算法 [24–27] . 将
数据点的邻域计算限定在子区域内部, 并行计算各数据点的近邻距离 [28,29] , 从而避免了各数据点相对于数据集内
2
所有数据点的距离计算, 将时间复杂度降低至 O(n ) 以下. 然而, 在子区域划分过程中, 已有的基于 GPU 的 DBSCAN
算法受到高维空间维度灾难的影响. 此外, 现有的基于 GPU 的 DBSCAN 算法并不支持基于图的索引结构, 对高维
向量数据的聚类效率低下.
因此, 为了突破 GPU 加速的高维向量聚类的技术瓶颈, 需要解决以下 3 个核心挑战.
(1) 如何高效构建近邻图索引. 引入近邻图索引可显著减小 DBSCAN 算法中的邻域计算代价, 且其对高维数
据的查询可保持较高的精度. 然而近邻图的构建需处理大规模距离计算与邻居列表的动态频繁更新. 现有的基于
CPU 的方法计算效率低, 而现有的基于 GPU 的方法仅将距离计算等操作转移至 GPU 设备, 邻居列表更新仍依赖
CPU 处理, 导致频繁的 PCIe 数据传输与同步开销.
(2) 如何高效划分大规模高维向量数据. K-means 树由于其简洁而高效的实现及不受维度灾难影响的特性而
成为对高维数据分区的流行方法 [30,31] . 然而, 随着分区粒度细化, 参与并行计算的数据点数量呈指数衰减, 致使
GPU 资源利用率降低, 造成资源利用与计算效率的双重恶化.
(3) 如何实现大规模高维向量的并行聚类. 在各分区的局部聚类阶段, 需设计基于 K 近邻图的高效并行遍历
策略, 以实现局部簇计算. 此外, 在局部簇合并阶段, 现有方法依赖于重叠分区检测并涉及大量串行操作, 严重制约
了 GPU 的并行吞吐量, 产生较高的合并开销.
为了解决上述挑战, 本文针对高维向量提出了一种基于 GPU 架构和 K 近邻图索引加速的 DBSCAN 算法 (KNN
graph-based and GPU-accelerated DBSCAN, KG-DBSCAN). 该算法首先利用 GPU 加速 K 近邻图索引的构建, 将
K 近邻图构建的全流程转移至 GPU, 并设计了偏好采样策略以加速近邻节点更新, 同时利用 GPU 加速高维向量