大规模图中最短路径查询方法研究

《大规模图中最短路径查询方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：学校代巧：１０１４０：密级：号ｍＱ勺ＵＱ公开学／ｉｒ１Ｃ？座婆卢、净ＬＩＡＯＮＩＮＧＵＮＩＶＥＲＳＩＴＹ硕±学位论文ＴＨＥ別ＳＦＯＲＭＡＳＴＥＲＤＥＧＲＥＥ培．梦论文题目：大规模图中最短路径查询方法研究ＲｅｓｅａｒｃｈｏｎＳｈｏｒｔｅｓｔＰａｔｈＱｕｅｒｙＭｅ１；ｈｏｄ英文题目；ｅ－Ｓｃａ化ｒＬａｒｌｅＧｒａｐｈｓｇ论文作者；王蠢■指导教师；宋宝燕教授专业＝计算机软件与理论完成时间—＝二〇六年五月申请狂宁大学硕击学位论文大规模图中最短路径查询方法研究Ｒｅｓｅａｒｃ

2、ｈｏｎＳｈｏｒｔｅｓｔＰａｔｈｕｅｒＭｅｔｈｏｄｆｏｒＱｙ－ＳｃａＬａｒｅｌｅＧｒａｐｈｓｇ：王基作者指导教师：東宝燕教授：计算机软件与理论专业答辩日期：２０１６年５月２５日二〇—六年五月．中国任宁巧宁大学学位论文原创性声明本人郑重声明：所呈交的学位论文是本人在导师的指导下独立完成的。论文中取得的研究成果除加Ｗ标注的内容外，不包含其他个人或集体已经发表或撰写过的研究成果，不包含本人为获得其他学位而使用过的成果。对本文的研究做出重要贡献的个人和集体均已在文中进行了标注，并表示谢意。本人完全意识到本声明的法

3、律结果由本人承担。〇学位论文作者签名：２ｌ年１月＞日ｌ学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部口或机构送交学位论文的原件、复印件和电子版，允许学位论文被查阅和借阅。本人授权迁宁大学可Ｗ将本学位论文的全部或部分内容编入有关数据库进行检索，可Ｗ采用影印、缩印或扫描等复制手段保存和汇编学位论文。同时授权中国学术期刊（光盘版）电子杂志社将本学位论文收录到《中国博±学位论文全文数据库》和《中国优秀硕±学位论文全文数据库》并通过网络向社会公众提供信息服务。学校须按照授权对学位论文进行管

4、理，不得超越授权对学位论文进行任意处理。），在年后解密适用本授权书。（保密：请在括号保密（＿＂＂内划Ｖ）授权人签名；指导教师签名；狡墓〇！＾曰親年１＞（》月１曰曰期：＞年／月７曰摘要图作为描述现实世界中实体及实体间关系的基本数据结构，被广泛应用于复杂网络分析、生物信息学、地理导航、物流规划等新兴领域。随着大数据时代的到来，图数据规模迅速増长，同时数据的拓扑结构也变得越来越复杂，导致大规模图数据的分析处理面临着巨大的挑战。最短路径查询是图论研究中的一核必内容之，现实世界中的很多问题都可Ｗ转化为最短路径问题求解。然而随着网

5、络规模的増大，经典的最短路径査询方法己无法满足大规模图的查询需求，设计更为有效的方法实现大规模图上的最短路径查询Ｗ满足各种应用需求具有一定的研究意义。本文对大规模图中最短路径查询方法进行了深入研究，发现无论是近似最短路径查询还是精确最短路径查询，在涉及大规模数据场景的现实应用中，预，预处理工作完成之后处理技术通常都被巧来作为提高査询效率的重要手段，查询算法通常能够Ｗ常数时间响应查询结果。因此，基于预处理的思想，本文首先提出了一种大规模图中近似最短路径査询方法，即关键点引导的近似最短路径查询方法，该方法选择Ｋ个顶点作为图中的关键点，预处理中只计算并存

6、储与关键点相关的最短路径，，可有效减少兀余数据量的存储同时提高预处理效率。在查询过程中，根据关键点估计最短路径，将源点与目的点之间的最短路径转化为源点与关键点之间，关键点之间，及关键点与目的点之间的最短路径之和，有，从而缩小了捜索区域的范围效提离最短路径的查询效率。然而＂＂关键点作为图中的枢纽顶点，最短路径查询通过关键点采用上确界方式估一计最短路径，本文方法会存在定的误差，但通过实验验证可Ｗ在可接受的误差范围内完成大规模图中的近似最短路径査询。为满足精确査询的需求并提髙预处理效率，本文提出了基于树分解与标签覆盖（ＴｒｅｅＤｅｃｏｍｐｏｓｉｔｉ

7、ｏｎａｎｄＬａｂｅｌＣｏｖｅｒ）的最短路径查询方法，该方法首先通过树分解将大规模图映射成树结构；其次在树分解基础上创建最小化的标签集合覆盖树结构，并优化树结构和距离标签结构，有效减少冗余数据存储并缩小遍，提高了预处理效率的同时降低了预处理开销，历顶点范围；最后在查询时利一一用预处理创建的索引结构，只需遍历次树结构即可完成查询，进步提髙了ｉ査询效率。最后，本文通过和已有的最短路径查询方法进行实验对比分析，验证了本文提出的两种最短路径查询