资源描述：
《不确定图数据查询处理技术的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、不确定图数据查询处理技术的研究作者：袁野东北大学东北大学博士学位论文摘要不确定图数据查询处理技术的研究摘要图是一种通用的数据结构，已应用到科学与工程的各个领域，如计算化学、生物信息学、流体动力学、社会关系学、万维网等。而现代科学的研究方法和测量技术普遍存在误差和噪声，使获取的图数据具有不确定性，例如不确定社会关系网络、不确定道路交通网络、不确定蛋白质交互网络、不确定本体网络等。近年来，不确定数据管理技术是数据库领域的研究热点，它的基本模型—可能世界模型—为建模不确定图提供了基础，使不确定图能充分表达研究对象的语义。现
2、有的确定图数据和不确定数据的管理技术不能用来处理不确定图数据，需要开发出新的技术。确定图数据之上的查询处理本身就非常复杂，甚至是NP-难题，如子图同构测试。另一方面，“可能世界”的规模呈指数级的增长。因此，如何高效地管理两者的结合体——不确定图更是难上加难。针对“不确定图的最短路径查询”，本文采用可能世界模型建模不确定图，基于该模型提出全新的最短路径查询定义——概率最短路径(P-SP)查询。首先为避免枚举指数级的可能世界，给出一个基本算法可精确求解P-SP查询。其次为进一步加速基本算法，用不确定事件界对基本算法中的解
3、决树进行剪枝；用同构图的缩减可以使基本算法只对图中相同的元素进行一次计算，从而降低计算空间；用不相交路径/割集界、关联界可使计算更快速地收敛。针对“不确定图的可达查询”，本文通过真实的应用实例说明此查询在生物网络、本体网络和RDF网络中有着广泛的应用。使用可能世界语义模型来定义概率可达查询(PR)，并证明处理PR查询是＃P-完全问题。为避免高昂的计算代价，首先给出一个基本随机算法可快速地估算出可达概率，并且该值有很高的精确度。为进一步完善基本方法，本文为随机算法引入条件分布，称为条件随机算法。在该算法中，采用图的不相
4、交路径集/割集、子图结果界作为条件概率－III－东北大学博士学位论文摘要分布应用于条件随机算法，因此改进的随机算法可准确地在多项式时间内处理查询。基于真实不确定图的大量实验验证了两种随机算法的正确性和高效性。针对“不确定图的子图查询”，本文使用可能世界模型描述不确定图中节点和关联边的概率依赖关系，进而定义了概率子图查询。尽管证明处理此查询是#P-完全问题，本文使用了一种“过滤-验证”的框架来有效地处理查询。在过滤阶段，通过最优子图特征选择方法构建概率索引(PIndex)，从而PIndex不仅具有小的尺寸，同时可最大限
5、度的剪枝不确定图。在验证阶段，给出了“基于迭代阈值”的精确算法可快速利用阈值结束计算。又给出“基于时间演化”的随机算法可高效准确地求解查询结果。大量的基于真实数据的实验验证了提出方法的有效性。针对“不确定平面图的模式匹配查询”，本文采用细粒度的可能世界模型来定义不确定平面图，从而使匹配查询具有丰富的概率语义。为避免枚举指数级的可能世界，首先设计了一个基于解决树的基本算法可精确地给出查询结果。对解决树中不确定事件提出了一种紧凑界限，从而进一步加速基本算法。最后基于模特卡罗理论设计出采样算法，可快速准确地估算查询匹配概率
6、。基于真实不确定平面图的实验验证了其有效性。关键词：不确定图,可能世界,最短路径查询,可达查询,子图查询,模式匹配查询－IV－东北大学博士学位论文AbstractStudiesonQueryProcessingTechniquesoverUncertainGraphDataAbstractGraphisageneraldatastructureandhasbeenwidelyusedinscienceandengineeringfields,suchascomputationalchemistry,bioinform
7、atics,fluiddynamics,socialrelationsandtheWorldWideWeb.However,thereexistnoiseanderrorsinmodernscientificresearchmethodsandmeasurementtechniques,whichleadstouncertaingraphs,suchasuncertainsocialnetwork,uncertainroadnetwork,uncertainprotein-proteininteractionnetw
8、orkanduncertainontologynetwork.Inrecentyears,uncertaindatamanagementhasbeenoneofhottopics,anditsbasicmodel,“possibleworlds”,laysafoundationformodelinguncertaingraphs,whichpr
