特征索引的大规模图子图查询方法研究

发布时间：2020-03-31 16:16

【摘要】：科技不断发展,各门学科与计算机领域的结合越来越紧密,图作为重要的数据结构,其应用范围不断拓广。蛋白质网络,社交网络以及电子商务网络等,都是以图进行建模的数据。随着互联网用户成倍的增加以及各门学科问题研究的深入,图数据规模逐渐增大,形成了复杂而又密集的大规模图结构,对海量图数据进行有效地管理和挖掘成为图数据研究的关键。近年来,在大规模图上进行子图查询的应用倍受关注,传统的子图查询方法适用于较小规模图的查询,如何优化大规模图结构的存储并高效的从海量图数据中查找出特定结构的子图成为当前研究的一项挑战。因此,本文利用索引查询的优势,提出了一种在图数据上建立特征索引的查询方法,线下提取结点特征,建立索引结构,线上进行索引遍历。基于这一索引,本文分别对星型结构和非星型结构两种查询模式进行研究,在非星型结构的子图查询中,定义了图的模式分解概念,并对中间解构建图模型,经过连接预处理后利用多连接方法计算最小代价确定连接顺序,得到最小规模候选集和尽可能小的查询结构,从而有效提高同构检测速度和查询效率。本文的研究成果主要有:(1)提出邻接点标数特征表的定义,将数据图结构转化为特征表的方式存储,结点的标签、度以及邻接点不同标签及其个数四项信息作为特征对数据图结点进行分类,根据分类原则将结点及对应的特征信息存储在特征表中。线下提取特征存储为特征表加快了索引的构建。(2)提出利用特征表构建邻接点双层索引Dulaq-Index的方法,根据特征表中结点的标签不同,每一类标签结点构建一棵特征索引树。根据特征表内特征间的包含关系分别设计上层索引和下层索引,根据邻接点标签个数是否唯一设计索引值,最终底层叶结点存储对应的数据图结点信息。实验表明该方法显著提高过滤效率,加速子图查询。(3)根据索引的特殊性,探究出星型结构子图的查询方法。提取星型查询图星心特征,通过遍历索引进行过滤得到结果集,再依赖存储结构的特殊性,对结果集展开得到最终查询结果。该查询算法极大提高了过滤能力并省略了对候选集的同构判别过程,与目前广泛应用的提取特征路径算法进行比较,有效缩短了子图查询时间。(4)针对非星型结构查询图的查询,提出结构的分解、子项过滤、中间解连接以及结果集同构判断的非星型图查询方法,定义了模式分解概念,提出基于图模型的中间解连接预处理方法,并结合MVP多连接查询算法,实现最小代价的中间解连接,得到的查询结果集是较小规模的图结构。再对结果集进行深度优先遍历得到最终的查询结果。实验证明该方法大大缩小查询图候选集,有效提高了查询效率。
【图文】：

标签图

图的规模也越来越大。在不同应环境下结查询是图论中经典的 NP 问题，因此在解决，从而探寻更适合当前情况的解决途径。据图和查询图：数据图是无向的、有标有如下：V 是结点集合；E 是无向边集；个结点的标签，其中 L (V) 。的、顶点标记的图，表示为 (,,,qqqqG VE (,,,)qqqq VE L对应字母的含义相同。本文。据图 G 的结点集 V (G)={v1,v2,v3,v,v4),(v1,v5),v2,v6),(v2,v7),(v2,v8),(v3,v4),(v4,v5),(v9,v3),(v{A,B,C},L(v1)=L(v2)=L(v3)=L(v4)=L(v6)==C.

结点,标签,和图

第 2 章相关工作同构：给定图 (,,,)qqqqqG VE L和图 G (V 有如下定义：对于任意结点qu V，，有 L(qqE，存在一条边 fufuEij( (),()) 。其中 f 表示)表示 Gq 结点的标签，ijq(u ,u) E表示 Gq 结是 Gq1 在 G 上的一个查询结果， f : v1 v4)，并找到 Gq1 每个结点每条边对应到 G 的图 G 上的映射 f 的结果 G1.
【学位授予单位】：辽宁大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.12

【参考文献】