动态有向图上面向最短路径查询的新型概要技术研究

《动态有向图上面向最短路径查询的新型概要技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文动态有向图上面向最短路径查询的新型概要技术研究作者姓名：王彪指导教师：谷峪副教授东北大学信息科学与工程学院申请学位级别：硕士学科类别：工学学科专业名称：计算机系统结构论文提交日期：2014年6月论文答辩日期：2014年6月学位授予日期：2014年7月答懒蝴：王大玲教授评阅人：夏秀峰教授张天成副教授东北大学2013年6月万方数据AThesisinComputerArchitectureResearchonNOVelSketchTechniquesforShortestPathQue

2、riesoVerDynamicDirectedGraphsbyW．angBiaoSupen，isor：AssociateProfessorGuY．uNortheasternUniversi姆June2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚的谢意。学位论文作者签名：王协日期：切

3、』牛·勿学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口学位论文作者签名：五船签字日期：矽，如石j

4、两年√导师签名：签字日期辔砂／秒砻眺万方数据东北大学硕士学位论文摘要动态有向图上面向最短路径查询的新型概要技术研究摘要近年来，随着有向图最短路径查询

5、应用在路网、计算机网络和社交网络等数据中的应用不断增加，有向图的最短路径查询技术受到更加广泛的关注。现有技术可以高效的处理无向图环境下的最短路径查询，然而由于有向图上最短路径查询操作的特殊性使得在有向图上的最短路径查询操作遇到了很大的挑战，有向图最短路径查询并无很好的解决方案。本文研究面向有向图准确的和带有精度保证的最短路径查询信息概要技术，并提出动态图环境下相应概要增量维护算法。首先，针对现有有向图最短路径查询技术在计算过程中在精度和速度上的缺陷，本文在代表点策略的基础上提出基于生成树编码概要结构，通过代表点

6、策略降低内存负载极大加快概要构建速度和查询速度；同时针对通过概要结构覆盖全部查询概要结构构建过程中频繁I／O的缺陷，改进其磁盘索引结构提出轻量级的概要结构；在证明准确概要查询结果有效性的前提下，本文提出了相应的I／O高效构建算法和查询算法，并通过实验对准确概要结构性能进行验证。其次，对于用户要求在短时间内获取带有误差保证最短距离的应用请求，本文提出基于拓扑层的离散landmark快速概要结构，通过laJldm冰节点的拓扑层次和相关信息，可以降低搜索数据大小并提前终结不必要的查询，进而加快查询速度；针对查询时在离

7、散landmark节点集合搜索代价较大的缺陷，本文依照二分索引思想组织laJldmark节点构建近似概要，并针对此概要结构提出近似概要构建算法和有精度保障的查询算法；最终在真实数据集和模拟数据集上进行大量的实验，验证近似概要结构和相应查询算法的有效性。最后，本文对概要结构的高效查询和动态图环境下概要增量维护操作进行研究，为了降低整体查询代价以及动态图环境下概要增量维护代价，本文设计离散磁盘结构存储Triad信息；同时在离散磁盘结构的基础上提出增量维护缓存结构降低平均增量维护代价，并通过摊还分析证明缓存结构的有效

8、性；最后提出基于离散磁盘结构信息获取算法和增量维护算法，并通过实验证明其有效性。本文从实际应用中对有向图最短路径查询的典型特征和调整进行分析，针对有向图最短路径概要相关技术进行研究，提出如代表点策略概要、有精度保障的近似概要以及概要结构增量维护等关键技术处理不同应用场景下的有向图最短路径查询应用。本文的概要结构以更少的内存和更短的预处理时间处理更大规模的图数据，并且以更快的速度返回最短路径查询结果。关键字：动态有向图；最短路径；概要技术；近似查询；增量计算万方数据东北大学硕士学位论文AbstractResear

9、chonNoVelSketch11echniquesforShortestPathQueriesoVerDynamicDirectedGraphsAbStractInrecentyears，shortestpathqueryondirectedgraphhasattractedinterestsofresearchersduetomultiplyshortestpathapplicat