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

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

后的结果返回 (第 9 行). 由于 edges 中边的数量远大于 k, 因此算法 4 整体的时间复杂度为 O(|edges|).

算法 4. 基于核心近邻图的簇合并算法.

输入: 簇编号表 Cid, 核心点集 C, 核心点所有距离小于等于 ε 的近邻 core_neighbors;
输出: DBSCAN 聚类结果.

1. edges ← ∅; /*集合, 位于 GPU 全局内存, 用于存放图中的边*/
2. for each p ∈ C in parallel at the thread block level do /*遍历所有核心点的邻居, 在节点间建立边*/
3. N(p) ← core_neighbors[p];
4. for each q ∈ N(p) in parallel at the thread level do /*遍历 p 的所有近邻*/
5. if q 为核心点且 q 与 p 位于不同分区 then /*若为其他分区的核心点, 则建立边*/
6. edges ← edges∪{(p,q)};
7. for each (p,q) ∈ edges do
, ,
8. union( Cid p q); /*合并 p 和 q 所代表的集合*/
9. return 聚类结果 Cid;

4 实验分析

本节使用 4 个真实数据集对所提出的算法进行评估, 并与相关算法进行对比. 第 4.1 节介绍实验数据集的相
关信息. 第 4.2 节介绍实验评估指标及基线对比算法. 第 4.3 节介绍实验参数设置. 第 4.4 节分别改变 ε 和 minPts
两个参数, 详细分析不同算法的聚类性能. 第 4.5 节对算法的可扩展性进行评估. 第 4.6 节对第 3 节中提出的 3 个
模块分别进行分析, 评估模块的有效性.
4.1 实验数据
本文使用 4 个真实数据集 (DEEP1M [50] 、SIFT1M [51] 、MSong (Million Song) [52] 、GIST [51] ), 数据集规模达到百
万级, 数据集的相关信息如表 1 所示.

表 1 数据集汇总

数据集名称 数据量 维度 数据大小 (MB) 默认 ε 默认minPts
DEEP1M 1 000 000 96 366.2 0.7 50
SIFT1M 1 000 000 128 488.3 200 50
MSong 992 272 420 1 589.8 20 10
GIST 1 000 000 960 3 662.1 1 50

4.2 基线算法与评估指标
● 基线算法. 本文将所提出的 KG-DBSCAN 算法与 5 种现有的 DBSCAN 算法进行了对比. 为了充分评估所
提出的基于 K 近邻图索引加速的聚类算法, 本文所对比的基线算法分别选择了采用树结构、HNSW 图结构以及
K 近邻图结构作为索引的 CPU 算法. 对于 GPU 算法, 现有的支持高维数据 DBSCAN 聚类的算法均未采用图索
引, 而分区聚类计算的 GPU 算法均采用网格或树结构进行分区, 面临维度灾难的问题 (第 1.2 节), 本文在可选的
GPU 加速的聚类算法中选择最新算法作为基线算法展开对比. 本文的基线算法具体包括: (1) BLOCK-DBSCAN [35] :
CPU 方法, 采用基于覆盖树的索引加速近邻查询; (2) h-DBSCAN [19] : CPU 方法, 采用基于 HNSW 的索引加速近邻
查询; (3) KNN-DBSCAN [22] : CPU 方法, 采用基于 K 近邻图的索引加速近邻查询, 使用最小生成树计算 DBSCAN
聚类; (4) Cal-DBSCAN [40] : GPU 方法, 利用 GPU 直接计算各节点的近邻而不使用任何索引; (5) cuML-DBSCAN [47] :
GPU 方法, 提供了随机球形覆盖索引和直接计算区域内数据点两种近邻搜索选项, 由于前者索引构建时间远大于
后者 DBSCAN 的计算时间, 因此在本文的实验中选择后者.