基于改进哈夫曼编码的大规模动态图可达查询方法研究

《基于改进哈夫曼编码的大规模动态图可达查询方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、：学校代码分类号：１０１４０：公开４０３１３３１９５０密级学号：？聲ＬＩＡＯＮＩＮＧＵＮＩＶＥＲＳＩＴＹ硕±学位论文ＴＨＥＳＩＳＦＯＲＭＡＳＴＥＲＤＥＧＲＥＥ基于改进哈夫曼编码的大规模动态图论文题目：可达查询方法研究ＲｅａｃｈａｂｉｌｉｔＱｕｅｒｙＢａｓｅｄｏｎＩｍｒｏｖｅｄＨｕｆｆｍａｎＣｏｄｉｎｙｐｇＯｖｅｒＬａｒｅ－ｓｃａＤｎａｍｒａｌｅｉｃＧｈ英文题目：ｇｙｐ论文作者：李正道宋宝燕教授指导教师＝计算机软件与理论专业

2、：二〇—六年五月完成时间：Ａ申请妊宁大学硕±学位论文基于改进哈夫曼编码的大规模动态图可达查询方法研究民ｅａｃｈａｂＵｉｔｕｅｒＢａｓｅｄｏｎＩｍｒｏｖｅｄＨｕｆｍａｎＣｏｄｉｎｙＱｙｐｇ－ＯｖｅｒＬａｒｅｓｃａｌｅＤｙｎａｍｉｃＧｒａｈｇｐ作者：李正道指导教师：宋宝燕教授专业：计算机软件与理论２０１６答辩时间：年５月２５日二〇－六年五月？中国辽宁迂宁大学学位论文原创牲声明本人郑重声明；所呈交的学位论文是本人在导师的指导下独立完成的

3、。论文中取得的研究成果除加标注的内容外，不包含其他个人或集体己经发表或撰写过的研究成果，不包含本人为获得其他学位而使用过的成果。对本文的研究做出重要贡献的个人和集体均已在文中进行了标注，并表示谢意。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名《月＞曰＾主凌年学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部口或机构送交学位论文的原件、复印件和电子版，允许学位论文被查阅和借阅。本人授权迁宁大学可Ｗ将本学位

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

5、摘要图数据能够有效描述现实生活中各类事物之间的复杂关系。随着社交网络分析、路由规划、生物信息网络分析和智能交通网络分析等新兴应用的涌现和计算机技术的飞速发展，，图的规模迅速增长，并且频繁更新使得对大规模动态图数据的处理需求愈加迫切。可达查询是图数据管理中的重点研究问题，应用领域广泛，现有的面向大规模动态图数据的可达查询研究成果较少，往往通，但大都存在索引压缩困难过索引来实现可达查询处理、图结构待优化、索引和图结构更新效率低等问题。一针对上述问题，本文提出了种支持大规模动态图的基于改

6、进哈夫曼编码－ｂａｓｅｄＬａｂｅ的可这查询处理方法（ＨｕｆｍａｎｌＲｅａ油ａｂｉｌｉｔｙ，ＨｕｆＬＲ。该方法首先对）一预处理图进行结构上的两次压缩，，得到双压缩图其次基于双压缩图提出；种前缀ｌａｂｅｌ索引，该索引能够有效表达节点间的可达关系最后，提出双压缩；图的演进和可达查询处理及优化算法，主要包括边的插入与删除、节点的插入与删除，ａｂｅｌ，。该方法具有良好的可行性和有效性不必给节点分配多重ｌ索引既减少了存储空间，又有效降低了ｌａｂｅｌ索引的初始化Ｗ及更新的复杂度。另外，，大大减

7、少了存储空间该算法还对图和索引进行了高度的压缩、处理复杂度和查询处理时图的规模。本文的贡献点可Ｗ概括如下：（１）提出双压缩图结构。首先运用ＤＡＧＤｉｒｅｃｔｅｄＡｃｙｃｌｉｃＧｒａｐｈ，ＤＡＧ压（）缩方法对图进行第一次压缩一；然后运用单链压缩方法对第次压缩的结果进行单链压缩，进而降低图的存储空间和查询处理时图的规模。一（２）提出种基于改进哈夫曼编码的前缀ｌａｂｅｌ索引及其压缩算法，能够有效表达节点间的可达关系，大大减少了索引的存储空间。〇）为了有效支持大规模动态图中的节点与边的变

8、化，提出了双压缩图的演进和可达查询处理算法，使得在图数据频繁更新的过程中，只需对部分数据，从而降低了查询复杂度进行调整即可。（４）在模拟数据集和真实数据集上进行了大量实验，验证了ＨｕｆＬ民方法在大规模动态图上实现可达查询处理的有效性和可行性，且具有良好的查询效率和较小的索引空间代价。Ｉ＾，：可达查询，哈夫曼编码，标签索引