不确定图上基于标签限制的可达性查询技术的研究

《不确定图上基于标签限制的可达性查询技术的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文不确定图上基于标签限制的可达性查询技术的研究作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：陈明涵于戈教授东北大学信息科学与工程学院硕士学科类别：工学计算机应用技术2013年6月论文答辩日期：2013年6月2013年7月答辩委员会主席：申德荣谷峪刘丽梅东北大学2013年6月万方数据AThesisinComputerApplicationTechnologyResearchonLabel-ConstraintReachabilit

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

3、’谚学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年／一年半口两年口学位论文作者签名：节、嘴魂致签字日期：矽一’匆、沈导师签名：j戈签字日期：>013．多．谚万方数据东北大学硕士学位论文简要不确定图上基于标签限制的可达性查询技术的研究摘要近年

4、来，图模型得到越来越多的重视，它不仅可以应用到路网及社交网络中，还可以应用到各种生物网络中。作为图上的基本查询之一，可达性查询得到了广泛的研究。可达性查询也是子图同构的图形查询的一个基本构成部分，因此可畿会被频繁调用以处理大量数据和复杂查询，对它的有效支持就显得尤为重要。然而，由于统计误差等原因，图数据往往具有不确定性，且随着图中包含的信息越来越丰富，各式各样的标签图应需产生。在这些图上的一个基础研究问题是基于标签限制的可达性查询(LCR)，即查询任意两点问路径满足标签集限制的可达概率。针对不确

5、定标签图，传统的可达性查询技术不再适用。针对上面提出的问题，本文对不确定图上基于标签限制的可达性查询技术进行了研究。首先，针对概率图的不确定性，本文形式化定义了不确定图上基于标签和距离限制的可达性问题，接着提出了一种基于子路径的高效的剪枝方法，根据子路径和距离阈值的特性，通过分支路径过滤的剪枝方法，大幅度减少了子路径处理个数。最后给出了抽样方法包括RandomWalk、不等概率抽样和DC树抽样方法。其次，针对标签集为有序限制的情况下，对上面的问题进行改进，定义了不确定图上有序标签限制的可达性查询

6、问题，由此提出了一个迭代算法，即使用路径索引及有效的剪枝方法定位含有有序标签的边，接着用这些边构造新的子路径，连接成完整路径并记录，再使用蒙特卡罗采样方法对所有路径的概率和进行估计，并给出了Bonferroni和Chung-Erdos不等式界和路径／割界。最后，实验通过比其他方法验证了本文所提出的算法在高效性和准确性上的优越性，同时检验了各种剪枝优化方法的效率。总之，本文从越来越接近实际应用的不确定图上基于标签限制的可达性查询的典型特征和挑战出发，针对不确定图上的路径标签的关键技术展开研究，如基

7、于子路径、路径索引的数据结构的标签查询技术，预处理技术、分支路径过滤技术和拓扑顺序剪枝技术等，从而提供高效健壮的不确定图上基于标签限制的查询处理方法。本文的研究工作所采用的算法思想和剪枝更新策略将为相关课题的开展打下了坚实的基础。关键词：标签；可达概率；子路径；路径索引；抽样；上下界万方数据东北大学硕士学位论文ResearchonLabel-ConstraintReachabilityQueriesinUncertainGraphsAbstractRecently,thegraphmodelha

8、sgainedincreasingattentionAsabasicqueryOngraphs，reachabmtyquerieshavebeenextensivelystudied．Itisalsoafundamentalcomponentofsubgraphisomorphicqueriesandissignificantlysupportedinthatreachabilityquerymaybefrequentlyinvokedtoprocesslargeamountsofdataand