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

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

个连接都有一种连接关系类型并连接两个不同对象,即 e=(o i ,o j ,r k ),e∈E,o i ,o j ∈O,i≠j,r k ∈R.
定义 2. G ON 中 o i 的对象数据Ψ 是通过访问互联网获取的 OBG 数据,包括对象本身和此对象产生的所有
i o
连接,可表示为 o i 以及 e i =(o i ,o j ,r k ),其中,e i ∈E,o i ,o j ∈O,i≠j,r k ∈R,全体对象的对象数据集合记为Ψ .
Ψ 包含 G ON 中的所有信息,所以获取 G ON 等价于获取Ψ .鉴于Ψ 对不同对象是独立可分的,因此可将 OBG 的
对象集合映射到高维空间,再对其进行子空间划分,这样就能在高维子空间中使用 QMC 采样来量化不同子空
间的重要性,从而进行自适应的 OBG 数据收集.
2.1 OBG高维空间映射与子空间划分
我们将 G ON 的对象集合 O={o 1 ,o 2 ,…,o |O| }映射到一个高维空间 A,|O|为 G ON 中对象的数量.映射后,第 i 个对
象的高维空间坐标可表示为
⎛ ⎛ i ⎥ ⎞ ⎢ ⎛ i ⎞ ⎢ ⎥ ⎛ i ⎥ ⎞ ⎢ ⎞
⎜ mod ⎜ ⎣ L ⎦ 0 ⎟ ⎢ ,mod ⎜ ⎥ ⎣ L ⎦ 1 ⎟ ⎢ ⎥ ,...,mod ⎜ ⎣ L h− ⎥ 2 ⎟ ⎢ ⎦ , ⎢ i ⎥ ⎟ (1)
⎜ ⎜ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎢ ⎣ L h− 1 ⎥ ⎟ ⎦ ⎟
⎝⎝ L ⎠ ⎝ L ⎠ ⎝ L ⎠ ⎠
|
其中,L 为 | O ,h 代表空间维度.
h
QMC 采样使用高维伪随机序列进行采样,高维空间 A 的维度 h 越高,QMC 采样的伪随机性和子空间覆盖
性越好,子空间分割也能够越精细,重要性计算的结果也越准确.对于 OBG 而言,恰当的 h 就足以表达其内部的
信息,多余的维度会造成计算资源的浪费.因此,对于复杂的 OBG,适当提高维度 h 将能够更快发现重要的子空
间,提升数据获取的效率.
A 中不同的子空间重要性不同,且这些子空间内不同的子空间重要性也不相同.为了计算子空间的重要性,
可将 A 分割为 K 个等大小的子空间,记为{A 1 ,…,A s ,…,A K },每个子空间也可继续划分,直到只包含单个对象.第 J

次划分结果表示为划分向量 k ,其每个维度取值为各个子空间该维度上等分分割份数的倒数.子空间的递归细
J
分将会产生一棵高度为 log K |O|的 K 叉树,根节点对应整个高维空间,第 1 层节点分别对应分割后的 K 个子空间,
其余层依此类推.例 1 展示了 OBG 的高维空间映射与子空间分割过程.基于此的分割方法,下一节将讨论如何利
用 QMC 采样递归的获取子空间重要性并进行自适应的数据收集.
例 1:设图 1 中社交媒体 OBG 对应的有向图为 G ON ={O,E,R},O={o 0 ,…,o 7 },E={e 0 =(o 2 ,o 1 ,r 0 ),…,e 8 },且 R={r 0 =
好友,r 1 =评论,r 2 =转发,r 3 =点赞}.若 h=3,根据公式(1)对 G ON 进行空间映射可得,o 0 ~o 7 对应坐标分别为(0,0,0),(1,0,
0),(0,1,0),(1,1,0),(0,0,1),(1,0.1),(0,1,1),(1,1,1).此时,OBG 将会被映射到一个三维的立方体内.对这个立方体进行
子空间分割,K=2 时先对 z 轴分割,则立方体在 x,y 和 z 这 3 个维度上分别被等分为 1 份、1 份和 2 份,对应的分

割向量为 k =(1,1,0.5),如图 2(a)所示.接着,用 k =(0.5,1,1)和 k =(1,0.5,1)对 x 轴和 y 轴划分,得到 8 个子空间,如
2
3
1
图 2(b)所示.后续分割过程类似,直到空间不再可分.
z z

0 0
x x
y y
(a) 仅 z 轴分割 (b) x,y 和 z 轴分割

Fig.2 Example of OBG projection and split
图 2 OBG 的映射与分割举例

2.2 基于采样的OBG数据收集算法
结合前述 OBG 的高维空间映射与划分方法,基于高维空间的 QMC 采样技术和分支限界方法,本节给出自
适应的 OBG 数据收集方法,包括子空间重要性评估和子空间选择两个阶段.