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

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

m
m+1
新节点 新节点 新节点 新节点 新节点

(a) 叶子节点在不同层 (b) 叶子节点在同一层
Fig.4 Iteration under different object numbers (white: iteration node, black: leaf node)
图 4 不同对象数下的迭代情况(白色节点为迭代节点,黑色节点为叶子节点)
(5) 冲突率
算法 1 在不同迭代节点对同一对象采样,则产生冲突,冲突越少,算法 1 执行的效率越高.冲突用冲突率表示,
记为
N conf
E conf = (8)
K
N iter ⋅⋅ | A s | R⋅ samp
其中,|A s |⋅R samp 是每次迭代过程中各个子空间的采样点数,N conf 是整个数据收集过程中的冲突总数.
定理 2 定量地描述了所有的冲突.
定理 2. 给定一个包含|O|个对象的 OBG,冲突总数为
1 ∑
P
N conf ∑ = N i= iter j= i m 1 ij (9)
i
i
i
其中,N iter 由定理 1 得出,m i =⎣log K |A |⎦,A 是第 i 次迭代的采样子空间,P ij 是子空间 A 对应的 K 叉树中第 j 层分割
得到的子空间中不重叠的冲突数.
证明:当算法 1 从 K 叉树自顶向下进行采样时,冲突最初从第 1 层迭代节点开始产生.
通过对子空间 A 中各级分割子空间中的非重叠冲突进行求和,得到第 i 次迭代的冲突数为 ∑ i m P ,那么该
i
j= 1 ij
1 ∑
过程的冲突总数为 ∑ N iter i m P .证毕. □
i= j= 1 ij
⋅
P .因此,冲
假设 K 叉树对应的各级采样子空间中的冲突数为一个固定的值,则 N conf 的近似值为 N iter ∑ j= i m 1 ij
突数以及 E conf 可通过调整 K 和 R samp 来降低.
3 基于泊松过程的 OBG 数据更新

3.1 数据更新概述
定义 3. 令 G ON ={O,E,R}为一个 T 时刻的 OBG,在 T′(T′>T)时为 G′ = {,O E′ ′ , }R′ .G ON 从 T 到 T′的增量可表
ON
示为
ΔG ON ={DIFF(O′,O),DIFF(E′,E),DIFF(R′,R)} (10)
DIFF(O′,O)可表示为 [O′ \ (O′ ∩ O )]∪ O \ (O′ ∩ O ) ,用来描述新加入与删除对象的集合,并以此作为 G′ 以
ON
及 G ON 之间的差异.ΔG ON 中,E 和 R 的增量可用类似方式表达.
根据定义 3,增量可以更具体表示为 O,E 和 R 集合中元素的添加和删除操作,因此增量可由定义 4 表示.
定义 4. 更新操作集合 U 包括添加和删除,分别记为 u 和 u .O,E 和 R 的更新操作集合分别记为 U O ,U E 和
U R ,ΔG ON ={U O ,U E ,U R }.
定义 5. 从 T 0 到 T 时刻收集的 OBG 数据中,统计窗口是 T 0 到 T 时刻内且结束于 T 时刻的时间区间,定义为
(T−α(T−T 0 ),T],如图 5 所示.其中,α称为窗口因子(0<α≤1).