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

3542 Journal of Software 软件学报 Vol.31, No.11, November 2020

给出 HD-QMC 算法的有效性、复杂度、标准误差、迭代次数和冲突率等指标的分析.
接着,借鉴基于历史数据统计的传统方法,本文结合信息熵、泊松过程 [12] 和前述的数据收集方法,提出数据
更新算法 EPP.作为数据收集方法的扩展,EPP 算法首先通过信息熵计算各个子空间的信息量,并利用泊松过程
预测每个子空间可能产生的增量,将 QMC 采样过程中得到的实际子空间增量的大小与预测增量的大小进行融
合,由此优先对增量较多的子空间进行采样,得到采样对象的增量,从而完成 OBG 数据的更新.
最后,我们基于 Spark 平台实现本文提出的算法,在真实数据集和生成数据集上,将 HD-QMC 和 EPP 算法与
现有方法在有效性和效率方面进行了对比,展示了本文方法针对实际应用中不同 OBG 数据的收集和更新效果.
与其他方法相比,本文的方法能更快地发现大多数重要的对象,且具有良好的可扩展性.

1 相关工作

• OBG 数据收集
通用爬虫和优先爬虫是主要的 OBG 数据收集工具.通用爬虫利用经典的广度优先 [13] 和深度优先 [14] 方法,
仅根据局部图结构进行数据收集.但 OBG 中各个部分的重要性在实际情况下并不相同,通用爬虫没有考虑到不
同部分重要性的差异.优先爬虫主要包括主题爬虫(topic crawler)和聚焦爬虫(focused crawler) [15] :主题爬虫根据
特定的主题从 Web 上搜索信息;聚焦爬虫通过使用基于应用、链接 [16] 和语义 [17] 的方法,在数据收集过程中能够
优先收集用户关注的内容,关注的内容可以是关键词或用户定义的其他需求.但是现有的优先爬虫大部分同样
由于受到 OBG 的在线性限制,主要关注局部图结构,为了快速发现 OBG 中重要的部分,还需要进一步扩展.与广
度优先和深度优先方法不同,本文方法并不是从 OBG 中的某个对象开始逐渐扩大收集范围,而是从 OBG 的全
局出发,优先收集重要部分中的数据.
• 基于采样技术的数据收集
使用这类方法可得到全局的图结构信息 [18] ,采样技术的引入,使得数据收集过程能够区别对待重要性不同
的部分,且采样技术与 OBG 数据收集还有很多结合点,例如,图流采样方法 [19] 从海量的图流数据中发现并收集
重要的图数据.但与本文方法不同,这种方法需要对所有图流数据进行分析,并不能在部分数据未知的情况下完
成采样.Yin 等人 [20] 提出一种基于 QMC 采样技术的聚焦爬虫,将 OBG 中的对象映射为一维向量,在此向量上,
通过 QMC 采样技术估算不同区域的重要性并收集数据.但是对于结构复杂的 OBG,一维映射会导致信息丢失,
影响重要性评估.另外,此方法对重要性的度量依据只有连接,对用户关注的其他信息表达不足.与上述方法不
同,本文通过将 OBG 中的对象映射到高维空间,并利用高维 Halton 序列生成采样点,提高了子空间重要性评估
的准确性,同时使用户可以选择需要的信息作为重要性评估的依据.
• OBG 数据更新
早期 OBG 数据更新的方法使用 Revisit [21] 策略,直接重新收集对象数据来替换本地已有数据.但是随着
OBG 数据的快速增长,导致每次数据更新会产生巨大的开销,并且不能满足数据更新的速度要求.为此,很多研
[8]
究专注于缩小收集范围来降低数据更新的成本.例如:Xi 等人 提出一种基于网页布局模式的方法,能够适用于
复杂的真实数据环境,借助网页布局模式来判断某一页面变化的可能性,但对于页面布局模式相似的对象来说,
[9]
并不能准确地为每个对象给出预测结果;Pavai 等人 根据历史数据计算每个对象发生变化的概率,但这种方法
无法预测历史数据中没有出现过的对象;Radinsky 等人 [22] 提出一种考虑了网页间连接结构的更新预测方法,通
过分析不同网页之间的结构关系,得出数据更新策略,但是随着网页间连接关系变得复杂,预测的准确性会受到
一定的影响;Cho 等人 [23] 提出基于采样的数据更新方法,通过对 OBG 某个部分进行少量的采样,判断其变化的
可能性,但该方法还不能用于自适应的数据更新.本文的数据更新方法建立在提出的数据收集方法之上,同时结
合了统计方法与 OBG 中的真实变化两个方面,能够快速且有效地更新已收集数据.

2 基于采样的 OBG 数据收集
定义 1. 一个 OBG 是一个有向图 G ON ={O,E,R},其中,O,E 和 R 分别是对象、连接和关系的集合.G ON 中的每