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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2026,37(3):1037−1057 [doi: 10.13328/j.cnki.jos.007512] [CSTR: 32375.14.jos.007512] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
GPU 加速的高维向量聚类算法

李忠根 1 , 龚盛豪 2 , 于浩然 1 , 朱轶凡 2,3 , 柳 晴 1,3 , 高云君 1,2,3

1
(浙江大学 计算机科学与技术学院, 浙江 杭州 310027)
2
(浙江大学 软件学院, 浙江 宁波 315048)
(全省大数据智能计算重点实验室 (浙江大学), 浙江 杭州 310027)
3
通信作者: 朱轶凡, E-mail: xtf_z@zju.edu.cn

摘 要: 聚类是大规模高维向量数据分析的关键技术之一. 近年来, 基于密度的聚类算法 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–2 822.5 倍.
关键词: 基于密度的聚类; 高维向量; GPU 加速; 并行计算; K 近邻图
中图法分类号: TP311

中文引用格式: 李忠根, 龚盛豪, 于浩然, 朱轶凡, 柳晴, 高云君. GPU加速的高维向量聚类算法. 软件学报, 2026, 37(3): 1037–1057.
http://www.jos.org.cn/1000-9825/7512.htm
英文引用格式: Li ZG, Gong SH, Yu HR, Zhu YF, Liu Q, Gao YJ. GPU-accelerated Clustering Algorithm for High-dimensional
Vectors. Ruan Jian Xue Bao/Journal of Software, 2026, 37(3): 1037–1057 (in Chinese). http://www.jos.org.cn/1000-9825/7512.htm

GPU-accelerated Clustering Algorithm for High-dimensional Vectors
2
2,3
1,3
1
1
LI Zhong-Gen , GONG Sheng-Hao , YU Hao-Ran , ZHU Yi-Fan , LIU Qing , GAO Yun-Jun 1,2,3
1
(College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China)
2
(School of Software Technology, Zhejiang University, Ningbo 315048, China)
3
(Zhejiang Key Laboratory of Big Data Intelligent Computing (Zhejiang University), Hangzhou 310027, China)
Abstract: Clustering serves as one of the critical technologies for large-scale, high-dimensional vector data analysis. Recently, a density-
based clustering algorithm DBSCAN (density-based spatial clustering of applications with noise) has been widely adopted in data analysis
due to their advantages of not requiring pre-specified cluster numbers, discovering complex cluster structures, and identifying noise points.
However, existing density-based clustering algorithms suffer from high computational costs when processing high-dimensional vectors.
Meanwhile, these methods also face challenges like the “curse of dimensionality”, restricting their practical applications. With the rapid
growth of high-dimensional vector data in the era of information technology, CPU-based clustering approaches encounter increasing

* 基金项目: 国家自然科学基金 (62025206, U23A20296, 62302444); 浙江省尖兵领雁项目 (2024C01259, 2025C01195)
李忠根和龚盛豪为共同第一作者.
本文由“向量数据库及 DB4LLM 技术”专题特约编辑高宏教授、李国良教授、张蓉教授推荐.
收稿时间: 2025-05-01; 修改时间: 2025-06-30; 采用时间: 2025-08-20; jos 在线出版时间: 2025-09-02
CNKI 网络首发时间: 2025-12-04