大规模图数据库中的模式查询算法研究

发布时间：2020-11-02 22:32

　　 近年来,随着图数据规模在各个应用领域的飞速增长,图模式查询引起了越来越广泛的关注。常见的图数据分为两种,第一种是大规模图数据,例如社交网络;第二种是海量图数据库,往往由大量规模较小的数据图组成,例如化学分子库。在本论文中,我们主要探索这两种不同数据库类型上的基础的图模式查询问题。在查阅了大量的已有研究工作之后,我们总结了几个基础且广泛应用的图查询问题,并且提出了相应的有效解法,提高了图模式查询的效率和可扩展性。本文的主要贡献总结如下:1.大规模图上的最大完全二分图模式查询。最大完全二分图问题,简称为MEB问题,在大规模图数据库中有着广泛的应用场景,例如,风险控制、机器学习、计算生物学等。给定一个二分图G,G由两个不相交的点集U和V组成,完全二分图C=(L∪R)是G中的一个子图,其中L?U,R?V,且满足L中所有的点和R中所有的点之间都有边。最大(边)完全二分图即G上边数量最多的完全二分图。MEB问题是一个NP完全问题,在大规模二分图上,现有的方法缺乏高效性和可扩展性。因此,我们提出了一种分层模型,将MEB问题分成多个子问题,并且通过在子问题中不断更新最大完全二分图的方式得到最后结果。在子问题中,我们设定了严格的完全二分图点集大小条件,以此来保证生成的完全二分图规模比当前已有的最大完全二分图规模更大,从而避免了不必要的计算。我们引进了两种高效的剪枝策略,根据点集大小条件压缩原数据图,从而极大的减少了搜索空间。我们进一步提出了贪心的完全二分图初始化算法,在初始化阶段尽可能找到大规模的完全二分图,为后续的计算和子问题中的点集大小条件提供更严格的范围界限,以提高搜索效率。我们在大规模真实数据图中做了大量的实验,实验结果显示,我们提出的分层算法比现有最好方法快几个数量级,同时,据我们所知,该分层算法也是当前唯一可以在十亿级别边的大规模图上计算最大完全二分图的方法。2.海量图数据库中的超图模式查询。超图模式查询是海量图数据库中的基础问题,在现实中有众多的应用场景。给定图数据库和查询图,超图查询在图数据库中查找所有包含在查询图中的结果。现有的方法大多遵循剪枝-验证的框架,但是在较大规模的数据图和查询图中,现有方法可扩展性较差。因此,我们提出了新的索引和查询方法,来处理超图模式查询问题。在索引阶段,我们直接根据数据图结构得到特征图,而不依赖于开销昂贵的频繁子图挖掘方法。在选择特征图的过程中,我们充分考虑了特征图的剪枝能力和计算共享能力,得到了各种规模的特征图组成的特征树索引。在超图模式查询过程中,我们根据查询图来衡量不同特征图的剪枝能力和计算共享能力,动态的选择最优特征图优先进行对比。我们还探索了两种优化策略,包括轻量的图压缩策略以及基于优先包含结果的策略,来进一步提高算法效率。最后,我们在两个真实数据集中进行了大量实验,实验结果表明,我们的方法具有高可扩展性。3.动态图数据库中的近似超图模式查询。海量图数据库由许多的数据图组成,为了在海量图数据库中高效的进行超图模式查询,现有方法往往是基于索引技术。然而,其中大部分索引算法都不适用于动态图数据库。在动态图数据库中,往往有频繁的图插入、删除以及修改操作。用户可以在更新后的图数据库上重建索引,但这样的方法非常耗费时间。另一方面,在动态图数据库中,随着时间推移,数据规模越来越大,精确的超图模式查询方法将面临效率问题。因此,基于这两方面的观察,我们提出了动态图数据库中的近似超图模式查询算法。在索引阶段,我们提出了在动态图数据库中增量更新图索引的方法。在图索引更新过程中,我们充分考虑了特征图的剪枝能力和计算共享能力。在查询阶段,我们提出了超图模式查询的近似算法,在大规模的数据图和查询图上极大的降低了计算开销,并且保证了高质量的查询结果。最后,我们在两个真实数据集中进行了大量实验,实验结果显示,我们的方法具有高效性和高可扩展性。
【学位单位】：华东师范大学
【学位级别】：博士
【学位年份】：2018
【中图分类】：TP311.13
【部分图文】：

图 3.3: LMEB算法的 (2,2)-MEB 求解例如，给定一个二分图 G（如图3.1(a)），以及 (2,2) 的点集限制条件，图3.3中示例了 LMEB算法求解 (2,2)-MEB 的过程。首先，假设我们初始化了一个完全二分图 Cmax= (L ∪ R)，其中 L = {u2, u3, u4, u5, u6}，R = {v2, v3, v5}，40

表 4.3: 参数设置参数 范围 默认值graph database size [3000,80000] 3000avg. node # of data-graph [10,90] 50avg. node # of query-graph [60,240] 100data-graph density group DG1, DG2, DG3, DG4, DG5–query-graph density group DQ1, DQ2, DQ3, DQ4, DQ5–组查询图分别记作 DQ1, DQ2, DQ3, DQ4和 DQ5。4.5.1分 数和优化策略性首先，我们测试了我们在索引和查询阶段提出的对特征图的打分函数的有效性。同时，我们也对比了基础的算法版本和有优化的算法版本，来查看图压缩策略和自适应节点分割策略的有效性。实验结果展示在4.4中。
【参考文献】

相关期刊论文 前1条

1 孙勤红;;支持增量图数据的超图查询算法研究[J];四川理工学院学报(自然科学版);2015年03期

本文编号：2867667