基于可达性的不确定图查询研究

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

1、硕士学位论文基于可达性的不确定图查询研究THEQUERYRESEARCHBASEDONREACHABILITYOFUNCERTAINGRAPH翟秋瑛哈尔滨工业大学2013年6月国内图书分类号：TP302.8学校代码：10213国际图书分类号：681.39密级：公开工学硕士学位论文基于可达性的不确定图查询研究硕士研究生：翟秋瑛导师：张炜申请学位：工学硕士学科：计算机科学与技术所在单位：计算机科学与技术学院答辩日期：2013年6月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP302.8U.D.C:681.39DissertationfortheMasterDegreeinEngi

2、neeringTHEQUERYRESEARCHBASEDONREACHABILITYOFUNCERTAINGRAPHCandidate：QiuyingZhaiSupervisor：WeiZhangAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：ComputerScienceandTechnologyAffiliation：SchoolofComputerScienceandTechnologyDateofDefence：June,2013Degree-Conferring-Institution：HarbinInstituteofT

3、echnology哈尔滨工业大学工学硕士学位论文摘要一直以来，图作为处理大规模数据的典型数据模型得到了广泛关注，比如蛋白质交互（Protein-ProteinInteraction,PPI）网络、交通网络、社交网络、RDF数据等都可以抽象为图。随着数据处理技术的提高，人们对数据的准确性要求也越来越高，数据采集和处理中带来的噪声和错误逐渐纳入研究范围，研究对象从确定型数据扩展为不确定型数据，模型也拓展为不确定图模型，即在确定图的基础上增加了概率维度。由于概率维度的增加，导致确定图中的研究成果不能直接应用于不确定图，需要探究新的方法。目前基于不确定图上的研究问题很多，比如子图匹配查询、最短路径查询

4、、可达性查询等，本文着重研究不确定图上基于距离阈值的可达性查询和基于概率阈值的模式匹配问题。针对不确定图上基于距离阈值的可达性查询问题，本文通过分析满足可达性条件的可能图实例的特点，定义了图实例分类树结构，给定任意可能图实例，根据遍历条件遍历图实例分类树，根据最终所达的状态便可知该实例的可达性。为了减小图实例分类树的信息冗余度，本文提出了基于双向遍历的优化分类树构造算法。最后本文设计了基于图实例分类树的抽样方法来估计基于距离阈值的不确定图可达概率，并通过理论分析和实验验证了算法的有效性。针对基于概率阈值的不确定图模式匹配的问题，目前完全相同的研究成果尚未出现，本文在给出问题定义的基础上，给出了

5、相应的解决方法：为了减小模式图的规模，在数据预处理阶段对模式图进行了化简；在基于概率阈值的可达性查询中本文采用filter-verify模式的判断方法加快了判定速率；最后给出了匹配查询过程算法并在合成数据和真实数据上验证了方法的有效性。关键词不确定图；可达性查询；图实例分类树；模式匹配I哈尔滨工业大学工学硕士学位论文AbstractAsatypicaldatamodeltodealwithlarge-scaledata,graphhasbeenwidelyconcerned.Manykindsofdatacanbeabstractedintographs,suchasproteinintera

6、ctionnetworks,socialnetworks,RDFdataandsoon.Withtheimprovementofdataprocessingtechnology,therequirementoftheaccuracyofdataisgettinghigher,andnoisesanderrorsindata'sacquisitionandprocessingareincludedintostudies.Withthesubjectextendingtouncertaindatafromcertaindata,themodelexpandstouncertaingraphmode

7、l,addingprobabilitydimensiontothecertaingraph.Duetotheincreasedprobabilitydimension,theresearchingresultsincertaingraphscannotbeappliedtouncertaingraphsdirectly.Soweneedtoexplorenewmethods.Thereareava