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

《特征索引的大规模图子图查询方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：单位代码：１０１４０１号公开学：４０３１５３１８８６？ＬＩＡＯＮＩＮＧＵＮＩＶＥＲＳＩＴＹ硕士学位论文ＴＨＥＳＩＳＦＯＲＭＡＳＴＥＲＤＥＧＲＥＥ论文题目：特征索引的大规模图子图查询方法研究ｒ－ＳｃａＲｅｓｅａｒｃｈｏｎＬａｅｌｅＧｒａｈＳｕｂｒａｈＱｕｅｒＭｅｔｈｏｄｇｐｇｐｙ英文题目：ＢａｓｅｄｏｎＦｅａｔｕｒｅＩｎｄｅｘ论文作者：高见野指导教师：宋宝燕教授专业：计算机软件与理论完成时间一：二〇八年五月辽宁大学学位论文原创性声明本人郑重声明

2、：所呈交的学位论文是本人在导师的指导下独立完成的。论文中取得的研究成果除加以标注的内容外，不包含其他个人或集体已经发表或撰写过的研究成果，不包含本人为获得其他学位而使用过的成果。对本文的研究做出重要贡献的个人和集体均已在文中进行了标注，并表示谢意。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：灰年Ｉ月分日］吣卿学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交学位论文的原件、复印件和电子版，允许学位论文被查阅和

3、借阅。本人授权辽宁大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编学位论文。同时授权中国学术期刊（光盘版）电子杂志社将本学位论文收录到《中国博士学位论文全文数据库》和《中国优秀硕士学位论文全文数据库》并通过网络向社会公众提供信息服务。学校须按照授权对学位论文进行管理，不得超越授权对学位论文进行任意处理？。保密（），在后解密适用本授权书。（保密：请在括年“”号内划Ｖ）授权人签名：指导教师签名：日期：年丨月此日日期：年Ｉ月必日申

4、请辽宁大学硕士学位论文特征索引的大规模图子图查询方法研究ResearchonLarge-ScaleGraphSubgraphQueryMethodBasedonFeatureIndex作者：高见野指导教师：宋宝燕教授专业：计算机软件与理论答辩时间：2018年5月二○一八年五月·中国辽宁摘要摘要科技不断发展，各门学科与计算机领域的结合越来越紧密，图作为重要的数据结构，其应用范围不断拓广。蛋白质网络，社交网络以及电子商务网络等，都是以图进行建模的数据。随着互联网用户成倍的增加以及各门学科问题研究的深入，图数据规模逐渐增大，形成了复杂而

5、又密集的大规模图结构，对海量图数据进行有效地管理和挖掘成为图数据研究的关键。近年来，在大规模图上进行子图查询的应用倍受关注，传统的子图查询方法适用于较小规模图的查询，如何优化大规模图结构的存储并高效的从海量图数据中查找出特定结构的子图成为当前研究的一项挑战。因此，本文利用索引查询的优势，提出了一种在图数据上建立特征索引的查询方法，线下提取结点特征，建立索引结构，线上进行索引遍历。基于这一索引，本文分别对星型结构和非星型结构两种查询模式进行研究，在非星型结构的子图查询中，定义了图的模式分解概念，并对中间解构建图模型，经过连接预处理后

6、利用多连接方法计算最小代价确定连接顺序，得到最小规模候选集和尽可能小的查询结构，从而有效提高同构检测速度和查询效率。本文的研究成果主要有：（1）提出邻接点标数特征表的定义，将数据图结构转化为特征表的方式存储，结点的标签、度以及邻接点不同标签及其个数四项信息作为特征对数据图结点进行分类，根据分类原则将结点及对应的特征信息存储在特征表中。线下提取特征存储为特征表加快了索引的构建。（2）提出利用特征表构建邻接点双层索引Dulaq-Index的方法，根据特征表中结点的标签不同，每一类标签结点构建一棵特征索引树。根据特征表内特征间的包含关系

7、分别设计上层索引和下层索引，根据邻接点标签个数是否唯一设计索引值，最终底层叶结点存储对应的数据图结点信息。实验表明该方法显著提高过滤效率，加速子图查询。（3）根据索引的特殊性，探究出星型结构子图的查询方法。提取星型查询图星心特征，通过遍历索引进行过滤得到结果集，再依赖存储结构的特殊性，对结果集展开得到最终查询结果。该查询算法极大提高了过滤能力并省略了对候选集的同构判别过程，与目前广泛应用的提取特征路径算法进行比较，有效I摘要缩短了子图查询时间。（4）针对非星型结构查询图的查询，提出结构的分解、子项过滤、中间解连接以及结果集同构判断

8、的非星型图查询方法，定义了模式分解概念，提出基于图模型的中间解连接预处理方法，并结合MVP多连接查询算法，实现最小代价的中间解连接，得到的查询结果集是较小规模的图结构。再对结果集进行深度优先遍历得到最终的查询结果。实验证明该方法大大缩小查询图候选集