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

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

implemented with Spark, and experimental results on simulated and real-world datasets show the effectiveness and efficiency of the
proposed method.
Key words: online big graph; data collection; data updating; parallel crawler; Spark

互联网中存在着大量有价值的非结构化数据,这些数据以不同的载体呈现,是内容全面的信息资源.图结构
是互联网中非结构化数据的一种主要组织形式,可表示为在线大图(online big graph,简称 OBG).典型的 OBG 包
括网页、社交媒体和知识图库,如图 1 所示.OBG 数据的获取,包括数据收集和更新,是解决大数据分析、知识工
[3]
程和决策支持等实际问题的重要前提和基础 [1,2] ,在 Web 搜索与海量数据分析 、数据集成 [4,5] 、数据抽取与融
[6]
合 等领域发挥着重要作用.一个 OBG 包括对象和连接,不同类型的 OBG 其对象和连接不同.
1 0 4 5
点赞 评论
链接 贾宝玉 角色 红楼梦
好友
3 转发
链接 链接 好友 转发 扮演 出演 类型
链接 链接
点赞
链接 2 6 7 欧阳奋强 古装剧
好友
网页OBG 社交媒体OBG 知识库OBG
Fig.1 Typical OBGs
图 1 典型的 OBG
[7]
OBG 中的数据具有海量、分布、异构和快速变化等特点 ,并且在数据收集之前,其全局的图结构是未知
的,这使得 OBG 数据的收集和更新都面临着数据量巨大、数据分布范围广、数据结构复杂且变化迅速等方面
的挑战,因此无法获取 OBG 中全部对象的数据.如何优先获取 OBG 中有价值、重要的数据,是一个在线优化问
题.解决这一问题主要面临如下难点和挑战:(1) OBG 数据的收集是在线(online)的,初始时,OBG 的结构完全未
知,随着收集到的数据不断增加,OBG 的结构才逐渐被发掘,在线性使得数据收集中对象的选取变得更加困难;
(2) 完全没有 OBG 数据的情况下,无法根据特定需求按照重要性由大到小的次序收集 OBG 中的对象,通过分析
已收集的 OBG 数据,发现重要对象的分布规律,也是提升后续数据获取效率的保证.因此,本文围绕如何优先收
集重要对象和利用已收集的 OBG 数据来优化其数据更新过程,讨论 OBG 数据的收集和更新方法,为 OBG 数据
处理与分析的相关问题奠定基础.
以通用爬虫(universal crawler)和优先爬虫(preferential crawler)为代表的 OBG 数据收集方法主要关注 OBG
[8]
的局部结构,但是针对数据收集过程的在线性,不能从全局出发寻找重要的数据;同时,基于网页布局 或历史数
[9]
据统计的 OBG 数据的更新方法 通过分析已收集的 OBG 数据得到变化规律,从而优化 OBG 数据的更新,但对
于数据变化规律并未包含于历史数据的情形仍不能有效更新.采样技术被广泛用于统计机器学习 [10] ,它能够方
便地处理全局性问题.半蒙特卡洛采样(quasi Monte Carlo sampling,简称 QMC)与传统的蒙特卡洛采样(Monte
Carlo sampling,简称 MC)技术不同,使用伪随机序列生成采样点,使得采样更加均匀和全面,避免了由于随机采
样点过近而导致重要性评估效果下降的问题.因此,以 OBG 数据的有效获取为目标,本文借鉴优先爬虫的思想,
基于 QMC 采样技术,提出自适应的 OBG 数据收集算法,并在其基础之上给出用于 OBG 数据更新的算法.针对
OBG 数据的海量性,我们利用 Spark 平台实现 OBG 数据的并行获取,保证 OBG 数据的高效获取.
首先,对于给定的 OBG,本文结合 QMC 采样技术和求解优化问题的分支限界方法,提出在线算法 HD-QMC,
从全局角度提升 OBG 数据收集的效果.我们将 OBG 对象集合映射到高维空间,并对高维空间分割得到子空间,
再利用 QMC 采样技术,先收集采样点对应的 OBG 对象,再由此评估各个子空间的重要性,对最重要的子空间递
归地执行上述过程,直到得到 OBG 中所有对象的数据,从而完成 OBG 数据的收集.然后,将已收集的数据统一表
示为 RDF(resource description framework)的形式 [11] ,为后续研究提供统一的数据接口.进一步地,本文从理论上