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

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

何操作. 之后, 由主线程取出队列头部节点, 进一步执行上述流程.
算法 3 展示了分区局部并行 DBSCAN 算法的具体流程. 该算法的输入为各个分区的点集合 S 、簇编号表
Cid、核心点近邻表 core_neighbors. 簇编号表 Cid 中存放每个点所属的簇编号, 以并查集的形式存储, 簇编号为
−1 的点代表噪声点. 核心点近邻表 core_neighbors 为二维数组, 用于存放所有核心点的距离小于等于 ε 的近邻点.
该算法首先初始化队列 queue 和集合 visited, 其中, queue 用于控制广度优先搜索过程中数据点的访问顺序, visited
用于标记元素以避免重复访问 (第 1、2 行). 随后, 启动多个线程块对每个分区独立并行聚类, 对每个分区而言, 算
法遍历分区内的所有点, 每次将未被访问的核心点入队, 并对其邻居进行扩展 (第 3–7 行). 接着, 算法持续迭代, 取
出队首元素 p, 并采用线程块中的所有线程对邻居列表 N(p) 进行并行扩展 (第 8–10 行). 每个线程处理一个近邻 q,
若 q 为非核心点, 则 q 可被分配给任何与 q 密度可达的簇, 因此可将 q 分配给 p 所在的簇. 若 q 为核心点, 则需判断
q 和 p 是否属于同一分区, 若在同一分区, 则把 q 合并到 p 所在的簇, 并将 q 入队 (第 11–20 行). 此外, 为了防止节
点的重复访问, 在处理过程中, 所有和 p 属于相同分区的点均被标记为 visited. 同时, 为了避免并发引起的竞争问
题, q 的入队采用可以避免并发写数据的原子操作完成. 最后, 算法返回完成单分区聚类的聚类结果 Cid (第 21 行).
由上述流程可见, 对于分区 S i 中的点, 若为非核心点, 则仅访问并标记, 若为核心点, 则需访问其邻居节点. 对于核
心点, 其邻居节点至多为 k (近邻图度数), 设每个线程块中线程数量为 threadNum, 则多线程并行访问邻居节点的
coreNum, 则算法
操作时间复杂度为 O(k/threadNum). 设 S i 中核心点数量为 3 的时间复杂度为 O((|S i |−coreNum)+
(coreNum×k/threadNum)), 即为 O(|S i |+coreNum×(k/threadNum−1)).
算法 3. 分区局部并行 DBSCAN 算法.

输入: 各分区点集 S , 簇编号表 Cid, 核心点所有距离小于等于 ε 的近邻 core_neighbors;
输出: 分区局部 DBSCAN 聚类结果.
1. queue ← ∅; /*队列, 位于共享内存, 用于 DBSCAN 过程的广度优先搜索*/
2. visited ← ∅; /*集合, 位于共享内存, 用于标记某点是否访问过*/
3. for each 分区 S i in parallel at thread block level do
4. for each p ∈ S i do /*遍历分区内所有点*/
5. if p ∈ visited 或 p 为非核心点 then /*若当前点已访问过或为非核心节点, 跳过该点*/
6. continue;
7. thread 0 do: p 入队列, visited ← visited ∪{p}; /*主线程将 p 入队列*/
8. while ( queue 非空) do
9. thread 0 do: 队首节点 p 出队列;
10. N(p) ← core_neighbors[p]; /*入队节点必为本分区核心点, 遍历其近邻进行簇扩展*/
11. for each q ∈ N(p) in parallel at thread level do
12. if q 为非核心点 then /*此时的簇从 p 开始扩展, 故将 p 设置为簇编号*/
13. Cid[q] ← p;
14. if q 位于当前分区 then
15. visited ← visited ∪{q};
16. else
17. if q 位于当前分区 then /*如果为当前分区的核心节点, 则入队*/
18. Cid[q] ← p;
19. visited ← visited ∪{q};
q 入队列;
20.
21. return 分区聚类结果 Cid;