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

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

的局部簇合并. 最后, 本文在 4 个真实向量数据集上对所提出的算法进行评估并与现有算法进行比较, 实验结果表
明本文所提出的算法在保证聚类质量的同时大幅提升了聚类效率. 然而, GPU 加速基于 K 近邻图的高维向量聚类
依然存在一些问题: (1) K 近邻图的构建代价随着 k 的增加而呈线性增长, 在算法设定中 k 需大于 minPts, 因此当
minPts 较大时将导致较高的索引构建开销; (2) 如第 2.2 节所述, 当节点间距离接近时, 算法存在将边界点识别为
噪声点的现象, 进而导致聚类精度降低, 需对聚类结果进行后处理以保证高精度的聚类. 未来将围绕上述问题展开
进一步研究.

References
[1] Mortensen KO, Zardbani F, Haque MA, Agustsson SY, Mottin D, Hofmann P, Karras P. Marigold: Efficient K-means clustering in high
dimensions. Proc. of the VLDB Endowment, 2023, 16(7): 1740–1748. [doi: 10.14778/3587136.3587147]
[2] Ester M, Kriegel HP, Sander J, Xu XW. A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proc.
of the 2nd Int’l Conf. on Knowledge Discovery and Data Mining. Portland: AAAI Press, 1996. 226–231.
[3] Gong SF, Zhang YF, Yu G. Clustering stream data by exploring the evolution of density mountain. Proc. of the VLDB Endowment, 2017,
11(4): 393–405. [doi: 10.1145/3186728.3164136]
[4] Abdulsahib AK, Balafar MA, Baradarani A. DGBPSO-DBSCAN: An optimized clustering technique based on supervised/unsupervised
text representation. IEEE Access, 2024, 12: 110798–110812. [doi: 10.1109/ACCESS.2024.3440518]
[5] Yang KY, Gao YJ, Ma R, Chen L, Wu S, Chen G. DBSCAN-MS: Distributed density-based clustering in metric spaces. In: Proc. of the
35th IEEE Int’l Conf. on Data Engineering. Macao: IEEE, 2019. 1346–1357. [doi: 10.1109/ICDE.2019.00122]
[6] Wang Z, Zhang R, Qi JZ, Yuan B. DBSVEC: Density-based clustering using support vector expansion. In: Proc. of the 35th IEEE Int’l
Conf. on Data Engineering. Macao: IEEE, 2019. 280–291. [doi: 10.1109/ICDE.2019.00033]
[7] Ma SQ, Kim C, Nam Y. Noise handling techniques in DBSCAN clustering for adult and child voice diarization. In: Proc. of the 2024 Int’l
Conf. on Platform Technology and Service. Jeju: IEEE, 2024. 23–26. [doi: 10.1109/PlatCon63925.2024.10830734]
[8] Gohil SH, Iorgulescu JB, Braun DA, Keskin DB, Livak KJ. Applying high-dimensional single-cell technologies to the analysis of cancer
immunotherapy. Nature Reviews Clinical Oncology, 2021, 18(4): 244–256. [doi: 10.1038/s41571-020-00449-x]
[9] Wang YQ, Gu Y, Shun JL. Theoretically-efficient and practical parallel DBSCAN. In: Proc. of the 2020 ACM SIGMOD Int’l Conf. on
Management of Data. Portland: ACM, 2020. 2555–2571. [doi: 10.1145/3318464.3380582]
[10] Wang MZ, Xu XL, Yue Q, Wang YX. A comprehensive survey and experimental comparison of graph-based approximate nearest
neighbor search. Proc. of the VLDB Endowment, 2021, 14(11): 1964–1978. [doi: 10.14778/3476249.3476255]
[11] Du MY, Li QM, Zhang M, Chen X, Li XM, Yin QJ, Ji SL. Constructing benchmark datasets for privacy-protected user comments and
evaluating the reasoning capabilities of large model. Chinese Journal of Computers, 2025, 48(7): 1529–1550 (in Chinese with English
abstract). [doi: 10.11897/SP.J.1016.2025.01529]
[12] Mo GL, Song SH, Ding H. Towards metric DBSCAN: Exact, approximate, and streaming algorithms. Proc. of the ACM on Management
of Data, 2024, 2(3): 178. [doi: 10.1145/3654981]
[13] Ding H, Yang F, Wang MY. On metric DBSCAN with low doubling dimension. In: Proc. of the 29th Int’l Joint Conf. on Artificial
Intelligence. 2021. 426.
[14] Schubert E, Sander J, Ester M, Kriegel HP, Xu XW. DBSCAN revisited, revisited: Why and how you should (still) use DBSCAN. ACM
Trans. on Database Systems, 2017, 42(3): 19. [doi: 10.1145/3068335]
[15] Jang J, Jiang H. DBSCAN++: Towards fast and scalable density clustering. In: Proc. of the 36th Int’l Conf. on Machine Learning. 2019.
3019–3029.
[16] Song H, Lee JG. RP-DBSCAN: A superfast parallel DBSCAN algorithm based on random partitioning. In: Proc. of the 2018 Int’l Conf.
on Management of Data. Houston: ACM, 2018. 1173–1187. [doi: 10.1145/3183713.3196887]
[17] Boonchoo T, Ao X, Liu Y, Zhao WZ, Zhuang FZ, He Q. Grid-based DBSCAN: Indexing and inference. Pattern Recognition, 2019, 90:
271–284. [doi: 10.1016/j.patcog.2019.01.034]
[18] Huang XG, Ma TF, Liu C, Liu SZ. GriT-DBSCAN: A spatial clustering algorithm for very large databases. Pattern Recognition, 2023,
142: 109658. [doi: 10.1016/j.patcog.2023.109658]
[19] Weng SY, Gou J, Fan ZW. h-DBSCAN: A simple fast DBSCAN algorithm for big data. In: Proc. of the 13th Asian Conf. on Machine
Learning. 2021. 81–96.
[20] Weng SY, Fan ZW, Gou J. A fast DBSCAN algorithm using a bi-directional HNSW index structure for big data. Int’l Journal of Machine
Learning and Cybernetics, 2024, 15(8): 3471–3494. [doi: 10.1007/s13042-024-02104-8]