软件学报

作者：李忠根，龚盛豪，于浩然，朱轶凡，柳晴，高云君

单位：李忠根，浙江大学 计算机科学与技术学院, 浙江 杭州 31002711,龚盛豪，浙江大学 软件学院, 浙江 宁波 31504802,于浩然，浙江大学 计算机科学与技术学院, 浙江 杭州 31002703,朱轶凡，浙江大学 软件学院, 浙江 宁波 315048;全省大数据智能计算重点实验室(浙江大学), 浙江 杭州 31002704,柳晴，浙江大学 计算机科学与技术学院, 浙江 杭州 310027;全省大数据智能计算重点实验室(浙江大学), 浙江 杭州 31002705,高云君，浙江大学 计算机科学与技术学院, 浙江 杭州 310027;浙江大学 软件学院, 浙江 宁波 315048;全省大数据智能计算重点实验室(浙江大学), 浙江 杭州 31002706

关键词：基于密度的聚类;高维向量;GPU加速;并行计算;K近邻图

基金：国家自然科学基金(62025206, U23A20296, 62302444); 浙江省尖兵领雁项目(2024C01259, 2025C01195)

聚类是大规模高维向量数据分析的关键技术之一. 近年来, 基于密度的聚类算法DBSCAN (density-based spatial clustering of applications with noise)因其无须预先指定聚类数量、能够发现复杂聚类结构并有效识别噪声点的特性, 在数据分析领域得到了广泛应用. 然而, 现有的基于密度的聚类算法在处理高维向量数据时将产生极高的时间代价且面临维度灾难等问题, 难以在实际场景中部署应用. 此外, 随着信息技术的发展, 高维向量数据规模急剧增加, 使用CPU进行高维向量聚类在时间代价和可扩展性等方面将面临更大的挑战. 为此, 提出一种GPU加速的高维向量聚类算法, 通过引入K近邻 (K-nearest neighbor, KNN) 图索引加速DBSCAN的计算. 首先, 设计了GPU加速的并行K近邻图构建算法, 显著降低了K近邻图索引的构建开销. 其次, 提出了基于层间并行的K-means树分区算法及基于广度优先搜索和核心近邻图的并行聚类算法, 改进了DBSCAN算法的计算流程, 实现了高并发向量聚类. 最后, 在真实向量数据集上进行了大量实验, 并将所提出的方法与现有方法进行了性能对比. 实验结果表明, 所提方法在保证聚类精度的前提下, 将大规模向量聚类的效率提高了5.7–2822.5倍.

来源：2026年第3期

《软件学报》期刊编辑部

查看软件学报杂志2026年第3期