基于双标签的大规模图的可达查询算法研究

《基于双标签的大规模图的可达查询算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码：１０１４０分类号：：４０３１３３１９７１密级：公开学号座宴乂聲ＬＩＡＯＮＩＮＧＵＮＩＶＥＲＳＩＴＹ硕±学位论文ＴＨＥＳＩＳＦＯＲＭＡＳＴＥＲＤＥＧＲＥＥ论文题目：基于双标签的大规模图的可达查询算法研究ＡｌｏｒｉｔｈｍｓＲｅｓｅａｒｃｈｏｆＲｅａｃｈａｂｉｌｋｙＱｕｅｒＢａｓｅｄｏｎｇｙｎ－ｏｕｂｌｅＬａｂｅｌｉＬａｒｅｓｃａｌｅＧｒａｈｓ英文题目：Ｄｇｐ论文作者：孙锐轩指导教师：宋宝燕教授专业：计算机应用技术完成时间二〇一六年五

2、月；申请辽宁大学硕壬学位论文基于双标签的大规模图的可达查询算法研究Ａｌｇｏｒｉ化ｍｓＲｅｓｅａｒｃｈｏｆＲｅａｃｈａｂ化ｔｙＱｕｅｒｙＢａｓｅｄｏｎＤｏｕｂｌｅＬａｂｅ－ｌｉｎＬａｒｅｓｃａｌｅＧｒａｐｈｓｇ作者：孙锐杆指导教师义宅燕教授：专业：计算机盧用技术答辩日期：２０１６年５月２５曰二〇—六年五月？中国迂宁迂宁大学学位论文原创性声明本人郑重声明：所呈交的学位论文是本人在导师的指导下独立完成的。论文中取得的研究成果除加标注的内容外

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

4、用影印、缩印或扫描等复制手段保存和汇编学位论文。同时授权中国学术期刊（光盘版）电子杂志社将本学位论文收录到《中国博±学位论文全文数据库》和《中国优秀硕±学位论文全文数据库》并通过网络向社会公众提供信息服务。学校须按照授权对学位论文进行营理，不得超越授权对学位论文进行任意处理。保密（），在年后解密适用本授权书。（保密；请在括＿＿＂＂号内划Ｖ）复授权人签名；丢乾指导教师签名：杉种日期：２０１６年６月２日日期：２０１６年６月２日搞要＂＂当今数据量増长的速度已经远远超出人

5、们的想象。图作为处理大规模数据的典型数据模型受到了研究领域的广泛关注，比如，生物网络、交通网络、社交网络、ＲＤＦ数据等等，都可Ｗ抽象为图。近年来，大规模图的可达查询研究成为当前研究的热点，尤其在大规模有向无环图上的查询技术受到了研究者的关注。随着图的规模越来越大，團数据的索引和査询技术面临新的挑战，对于查询的准确性和效率的要求越来越高。同时，已知的可达查询技术往往适用于中小规模的图数据一些可Ｗ适用，对大规模图数据的处理表现不尽人意，而于大规模图的查询技术又很难在查询效率、索引构建时间和系统存储占

6、用上得一到平衡。所Ｗ，，找到种新的查询方法既可Ｗ适用于大规模图上，又能在查询效率、索引构建时间和系统占用上取得相对的平衡成为了本次研究的出发点。一为了更好地在大规模图上进行可达查询，本文提出了种新的双标签索引的查询算法（ＴＳＩＬ）。该方法建立在对点的级别划分上。首先在对图进行遍历之后，通过计算每个点的出入边情况，得到点的权值，把主要关注的点定义为一权值点，权值点代表了其周边系列有类似属性的点，涵盖了部分点的特征，同时为不同的权值点定义不同的索引结构。送样划分的优点在于查询时可Ｗ优一先查找有

7、代表性的权值点，，再通过权值点进行小范围查询定程度上提高了查询的效率，并确保在大规模图上依然可Ｗ快速查询。同时，针对大规模图上可能出现的某些点的可达性比较集中的情况，提出了该双标签索引的改进算法（ＴＳＩＬ＋ｅ），简化查询步骤，Ｗ达到节省索引空间和快速查询的目的。最后，通过对比实验，测试该算法与其他己知算法在相同图上的表现，验证本文所提出的ＴＳＩＬ方法对查询效率的提高，并检验优化算法在大规模图与其他已知算法在查询时间，索引构建时间和系统占用的优越性。总之，本文为了达到可Ｗ在大规模国上进行可达查询的

8、目的，在分析了单标签与双标签在图规模很大的情况下的表现优劣，针对双标签索引查询快但不适用大图的特点进行了深入研究，从而使双标签可达性索引能够更好地应用在大规模图数据上。关键词：，，双标签索引大规模图可达查询，权值点ＩＡｂｓｔｒａｃｔＡＢＳＴＲＡＣＴ＇ｅ＇Ｔｈｉｎｃｒ