大图上高效的子图匹配算法设计与实现

《大图上高效的子图匹配算法设计与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、＇－Ｉ；＇、．如－１．．；Ｖ弟Ｔ：？＇．．．．＇．＇．．‘．／．難薄．’？？＇■－；＃Ｖ一Ｉ飞：’分类号．．．．．．．．．．．．．’一又舞户＾ｆ；ＪＰ綱副硕－上研究生学位论文大图上高效的子图匹配算法设计与实现申请人：纪安娜＇＇‘学号－：２１４０巧培养单位；计算化科学技术学院学科专业：软件工程研巧方向：数据挖掘指导教师：杨艳教授完成日巧：２０１６年３月２６日■．独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研巧

2、工作及取得的研究成果。据我所知，除了文中特别加Ｗ标注和致谢的地方外，论文中不包含他人已经发表或撰写过的研究成果，也不包含为获得黑龙江大学或其他教育机构的学位或证书而使用过的材料一。与我同工作的同志对本研究所作的任何贡献均已在论文中作了明确地说明并表示谢意。＞八年＾＾学位论文作者签名：签字日期：月可記１每学位论文版权使用授权书本学位论文作者完全了解墨龙狂去堂有关保留、使巧学位论义的规定，有权保留并向国家有关部口或机构送交论文的复巧件和滋盘。，允许论文被查阅和借阅本人授权黑龙江大学可Ｗ将学

3、位论文的全部或部分内容编入有关数据库进行检索，可采用影印、缩论印文或扫描等复制手段保存、汇编学位论文。（保密的学位在解密后适用于本授权书）学签位论文作者签名：导师签名；字曰期；２。／缸細６曰签字曰期：年細＾曰学工位论文作者毕业后去向：通作讯单地位址：电话：：邮编：分类号UDC密级公开硕士研究生学位论文大图上高效的子图匹配算法设计与实现申请人:纪安娜学号:2141353培养单位:计算机科学技术学院学科专业:软件工程研究方向:数据挖掘指导教师:杨艳教授完成日期:2016年3月26日中文摘

4、要在大数据时代，海量多源异构数据之间存在着复杂、紧密的关系，用图结构作为描述数据间复杂的关系被广泛应用于各个领域。但是，随着这些领域的蓬勃发展，以图为结构的数据量也呈指数型爆炸式增长。而子图匹配作为图数据处理中的一项基本操作，备受学术界和工业界所关注。如何根据用户自定义的查询结构，在大规模数据图上高效地返回满足用户要求的匹配成为目前首要研究问题。然而，之前的工作，多数都是在无权图上的查询，并没有考虑用户的个性化需求，并且目前算法在大规模数据图上的执行时间和效果并不是很理想。本文对目前子图匹配问题中的存在的不足进行了改进和

5、创新，主要研究成果及贡献如下：对于大规模数据图上的个性化子图匹配算法进行研究，首先通过已有的社团检测GN算法将数据图划分成若干个子区域，2个线下索引结构：GP-Tree索引和排序边集索引；然后基于索引结构，通过增加优化策略来加速子图匹配；最后，通过实验证明了该算法的有效性和扩展性。对于大规模数据图上的并行子图匹配算法进行研究，利用SparkGraphX中的顶点划分算法将数据图进行划分，保证每台计算机上数据的负载均衡；并通过建立GP邻接索引和排序边集索引，在Spark集群上来实现并行子图匹配算法；最后，通过大量实验验证该算

6、法在大规模数据图上的高效性和扩展性。关键词：子图匹配；子图同构；图模式匹配；图分割；图数据-I-AbstractIntheeraofbigdata,thereisamassivemulti-sourceandheterogeneousdatawithcomplexandcloserelationships,usingthegraphstructureasdescribedcomplexrelationshipsamongdataarewidelyusedinvariousfields.However,withtherap

7、iddevelopmentofthesefields,theamountofdatausinggraphstructureisalsoexponentiallyexploding.Andsubgraphmatchingasthebasicoperationingraphprocessing,getabundantattentionfromacademiaandindustry.Recently,howtoefficientbaseonuser-definedquerystructuretogetmatcheswhichm

8、eetuser-definedrequirementsonlarge-scalegraphbecomeaprimaryproblem.Andpreviousworkonsubgraphmatchingdon’tconsideruser-definedrequirementsforsomespecialedgessot