| 引用本文: | 李忠根,龚盛豪,于浩然,朱轶凡,柳晴,高云君.GPU加速的高维向量聚类算法.软件学报,2026,37(3):1037-1057 |
| |
|
| |
|
|
| 本文已被：浏览 1627次 下载 1255次 |
码上扫一扫！ |
|
|
| GPU加速的高维向量聚类算法 |
|
李忠根1, 龚盛豪2, 于浩然1, 朱轶凡2,3, 柳晴1,3, 高云君1,2,3
|
|
1.浙江大学 计算机科学与技术学院, 浙江 杭州 310027;2.浙江大学 软件学院, 浙江 宁波 315048;3.全省大数据智能计算重点实验室(浙江大学), 浙江 杭州 310027
|
|
| 摘要: |
| 聚类是大规模高维向量数据分析的关键技术之一. 近年来, 基于密度的聚类算法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倍. |
| 关键词: 基于密度的聚类 高维向量 GPU加速 并行计算 K近邻图 |
| DOI：10.13328/j.cnki.jos.007512 |
| 分类号:TP311 |
| 基金项目:国家自然科学基金(62025206, U23A20296, 62302444); 浙江省尖兵领雁项目(2024C01259, 2025C01195) |
|
| GPU-accelerated Clustering Algorithm for High-dimensional Vectors |
|
LI Zhong-Gen1, GONG Sheng-Hao2, YU Hao-Ran1, ZHU Yi-Fan2,3, LIU Qing1,3, GAO Yun-Jun1,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 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–2822.5 times while maintaining clustering accuracy. |
| Key words: density-based clustering high-dimensional vector GPU acceleration parallel computing K-nearest neighbor (KNN) graph |
|
|
|
|
