大规模动态有向标签图子图查询方法研究

《大规模动态有向标签图子图查询方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：单位代码：１０１４０密级：：４０３１公开学号１５３９００◎ＬＩＡＯＮＩＮＧＵＮＩＶＥＲＳＩＴＹ硕士学位论文ＴＨＥＳＩＳＦＯＲＭＡＳＴＥＲＤＥＧＲＥＥ中文题目：大规模动态有向标签图子图查询方法研究ｒｈｒＬａｒｅ－ｓｃａＲｅｓｅａｃｈｏｎＳｕｂｒａＱｕｅｒＭｅｔｈｏｄｆｏｌｅｇｐｙｇ英文题目：ＤｎａｍｉｃａｎｄＤｉｒｅｃｔｅｄＬａｂｅｌＧｒａｈｙｐ论文作者：姜丽雁指导教师：宋宝燕教授专业：计算机软件与理论完成时间一：二○八年五月＊申请辽宁大学硕士学位论文大规模动态有向标签图子图查询

2、方法研究ResearchonSubgraphQueryMethodforLarge-scaleDynamicandDirectedLabelGraph作者：姜丽雁指导教师：宋宝燕教授专业：计算机软件与理论答辩日期：2018年5月22日二○一八年五月·中国辽宁辽宁大学学位论文原创性声明本人郑重声明：所呈交的学位论文是本人在４师的指泞下独立完成的。论文中取得的研究成果除加以标汴的内容夕卜，小乜舍从他个人？或集体已经发．丧或撰写过的研究成果，小包ｒｖ木人为获以ｋ他９位而使叫过的成果。对本文的研究做山重要ｇ献的个人和ｔｕ体均己在文屮进行ｒ标注，并表示谢意。

3、本人宂全总识到木声叨的法栉结米山木人廣礼学位论文作者签名：名補涯年学位论文版权使用授权书：、本学位论文作者完个丫解７校打又保留侦学位论文的规定，同意学校保留并向国家心又邰门成机构送交，位论文的原件、复印件。ｎ和电子版，允许学位论文被作阅和仍阅本人授权辽宁人学ｊ以将木－ｎ、学位论文的个部或部分内容编入打又数据库进行检索，ｊ以來用影印？缩印或扫描等Ｍ制丁段保介和爿：编学位论文。学校须按照授权对学位论文进行宵理，＋得超越授权对７位论文进行任意处理。）６保密（，在年Ｇ解密适用木授权书（保密：请在括号“”内划Ｖ）授权人签

4、名ｇ指导教师签名ＩＩ期：年ｓ月乃ｎ丨」期：？年５爿名ｎＡ／％摘要摘要随着计算机应用领域的丰富与扩展，图作为常用的数据结构之一，现实世界的诸多领域均用图来描述其复杂而庞大的逻辑关系，如社交网、生物信息网、智能交通网等新兴领域的建模。同时在某些复杂网络中存在多种类别的顶点，常利用标签图对此类复杂网络进行建模。如社交网中的微博，我们可以用顶点表示微博用户，任意用户之间的关注情况可通过有向边来表示，此时标签可用来表示用户的性别、所在地、关注领域等信息。子图查询作为图数据分析的关键问题，引起了研究者的广泛关注。动态标签图子图查询，即返回结构及标签值均同构于查询图

5、的若干子图。然而子图同构查询是一个NP完全问题，随着数据图的增长且频繁更新，查询时间会大大增加，通过创建高质量的索引结构以提高查询效率已成为解决这一问题的关键。例如：微博新用户的注册、老用户的注销、用户间新增或取消关注等行为都会导致标签图的动态变化。微博应用中新用户注册、用户添加关注等行为都将抽象为标签图顶点或边的插入，微博中用户账号注销，取消关注等行为都将抽象为标签图中顶点或边的删除。对现有子图查询算法的研究发现，随着图数据规模增大且频繁更新，传统子图查询算法普遍存在查询效率低、存储开销大、忽略顶点标签信息等问题。为此，本文主要对大规模动态有向标签图的子图查询问题进

6、行研究，本文主要内容可概括如下：（1）提出动态层次序列索引，即DHS索引。该索引利用有向无环图的偏序关系将顶点拓扑成层次序列，同时在各层序列中加入顶点编号信息，不需要提取复杂特征关系即可实现快速准确地查询。（2）针对图动态变化导致的索引变化，提出更新点拓扑扩展式索引维护策略。该策略采用增量式更新方式，仅从局部变化顶点或边进行拓扑扩展以实现对索引的动态维护，从而降低重新构建全局索引带来的巨大开销。（3）针对动态有向标签图的子图查询-SubDBGragh，提出了基于DHS索引的子图查询方法。该方法将查询图与数据图的层次序列进行逐层匹配，以过滤大量非匹配项的干扰，获得候选集

7、，相对于图的匹配，序列匹配较为简单，可以减少同构检测的次数，从而提高查询效率。同时本文提出一种关系匹配策略用以对I摘要候选集中的边进行关系匹配以获得最终详细的查询结果图。（4）针对大规模SubDBGragh的分布式处理问题，提出分割数据集和局部层次序列索引（LDHS索引）的建立。用分割数据集存储割点及割边的信息，在进行数据处理之前把分割数据集信息加载到各分区中，在进行子图查询时分割数据集辅助相关分区完成查询操作。该方法的好处的是在查询执行时不需要同时访问多个分区的数据信息，只需要在相应的分区执行需要的查询操作，最终将查询结果连接合并成完整结果，有效的