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

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

第ε个采样点的增量大小,则融合后的 K 叉树中第 l 层第 j 个子空间的增量密度表示为
⎛ V′ jl (1)− ⎞
V jl (1 β ′ = − )V + jl β ⎜ (0≤ β ⎟ ≤ 1,l > 1) (13)
⎝ K ⎠
V′ jl (1)− 为包含当前子空间的上一级子空间增量密度,即 K 叉树中当前迭代节点的父节点对应子空间的增量
密度.特别地,V′ = U j /| B .
|
1 j
j
上述思想见算法 2.
算法 2. EPP.
c
输入:初始增量密度最大的子空间 A max ,K,R samp ,Ψ ,包含所有子空间增量密度初始值的 P cand .
c
输出:更新后的Ψ .
步骤:
IF |A max |>1 AND ρ ≥ ρ min THEN
S←Divide(A max ,K) //K 个子空间与已收集数据相同
FOR EACH s IN S DO
vol←0
W←HaltonSeq(s,R samp ) //生成采样点集合 W
FOR EACH w IN W DO
obj←Collect(w)
c
c
temp←Find(Ψ ,w) //在Ψ 中查找 w
IF obj≠temp THEN
vol←vol+IncVol(obj,temp) //计算增量大小
c
c
Update(Ψ ,w,obj) //用 obj 更新Ψ 中的 w
END IF
END FOR
IF |s|>1 THEN
density←(1−β)⋅vol/|W|+β⋅HistoryDensity(⋅)
P cand .Add([s,density])
END IF
END FOR
A max ←P cand .PickMax(⋅) //取出下一个子空间
EPP(⋅) //下一次迭代
END IF
与算法 1 类似,同样使用 QMC 采样技术来发现全部增量,包括新的对象、连接和连接类型.算法 2 中的 IncVol
计算当前采样点的增量大小.HistoryDensity 用于得到当前子空间的V′ / K .算法 2 与算法 1 的时间复杂度相
jl (1)−
同,都为 O(|O|⋅log|O|).算法 2 的执行过程可由例 3 表示.
c
例 3:基于例 2 得到的Ψ ,令α=1,β=0.2.若新产生的数据为 e 9 =(o 3 ,o 4 ,r 2 ),e 10 =(o 4 ,o 5 ,r 3 ),e 11 =(o 5 ,o 6 ,r 0 ),根据定义
B
6, G ON 中 O,E 和 R 的信息熵分别为 H(O)=0.903,H(E)=0.954,H(R)=0.553.
数据更新过程如图 6 所示,子空间划分方式及采样序列与例 2 一致,图中节点下部左侧与右侧各代表V′ 和
jl
V jl .算法优先选择融合后增量密度最大的节点进行迭代,顺序由图中的标号给出,其中,对 o 4 ,o 5 和 o 3 的采样过程
中发现了新数据 e 10 ,e 11 和 e 9 ,并将其加入到已收集数据中,已收集数据与当前 OBG 上的数据保持同步.