Page 230 - 《软件学报》2020年第11期

尹子都 等:基于采样的在线大图数据收集和更新 3545

IF |A|>1 AND ρ ≥ ρ min THEN
S←Divide(A,K) //分为 K 个子空间,得到集合 S
FOR EACH s IN S DO //s 为子空间
mass←0
W←HaltonSeq(s,R samp ) //生成采样点集合 W
FOR EACH w IN W DO
c
IF w∉Ψ THEN
obj←Collect(w)
c
c
Ψ ←Ψ ∪obj
END IF
mass←mass+NumInfo(obj) //加入新增的目标信息数量
END FOR
IF |s|>1 THEN
density←mass/|W|
P cand .Add([s,density])
END IF
END FOR
A←P cand .PickMax(⋅) //取出密度最大的子空间
HD-QMC(⋅) //下一次迭代
END IF
算法 1 中的 FOR 循环可并行完成.算法迭代执行,对子空间进行分割并产生一棵 K 叉树,每个非叶子节点代
表一次迭代并对应一个子空间,每次迭代将从一个非叶子节点产生 K 个分支,对原来子空间进一步划分,并产生
新的子空间.子空间不可分,则为叶子节点且不产生新的分支.例 2 给出了基于算法 1 的 OBG 数据收集过程.
例 2:基于例 1 得到的高维空间 A 及其子空间,以社交行为“关注”“转发”“评论”“点赞”作为目标信息,则子空
间的重要性取决于对象的出度,整个数据收集过程将进行多次 QMC 采样迭代并生成一棵二叉树,其上部为子
空间内的所有对象,下部表示子空间的目标信息密度,分支上标注了 QMC 采样点对应的对象,如图 3 所示.二叉

树中的第 1 层~第 3 层节点对应的子空间,分别由上层节点对应的子空间经过分割向量 ,,kk k 分割得到.算法优
2
1
3
c
先选择目标信息密度最大的节点进行迭代,执行顺序为图中序号,最终得到所有对象数据集合Ψ .
1
--
o 0~o 7
--
o 1,o 3 o 5,o 7
2 6
o 0~o 3 o 4~o 7
=1 =0.5
o 0 o 1 o 4 o 5
3 5 7 9
o 0,o 2 o 1,o 3 o 4,o 6 o 5,o 7
=2 =1 =1 =1
o 2 o 6
4 8
o 2 o 6
-- --

Fig.3 Example of data collection
图 3 数据收集过程举例