基于不确定平面图的模式匹配查询的分析与实现

《基于不确定平面图的模式匹配查询的分析与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据盘i垦盘堂塑±鲎焦迨塞旦垂4．1基于不相交匹配／N集界的算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯394．2基于同构图缩减的算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯424．3基于不确定事件界的算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯454．4采样算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯464．5实验分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯484。5．1真实数据实验⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．484．5．2合成数据实验⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．504．6本章小结⋯

2、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯51第5章结论与展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯535．1总结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．535．2展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．53参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．55致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．59攻读硕士期间发表的论文和参加的项目⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．61．VI．万方

3、数据第1章绪论近年来，由于科学技术的不断发展，以及互联网技术的不断进步，使得数据以及数据查询操作的数量猛增，当今，人类拥有的知识以及数据信息量每隔5年就要翻一番，而到21世纪20年代，知识与信息翻一番的周期将锐减到70天左右，而随着时间的推移，周期必然继续减小【l】。由上述可知，存储这样海量数据的方法是当今计算机领域亟待解决的重大课题。所以在过去的许多年里，传统的数据管理(DataManagement)技术得到了很好的发展，而这些研究都是针对确定数据(CertainData)的，这些研究成就了一个上百亿的产业一数据库产业。而建设信息化社会的一个重要支撑就是数据库技术

4、以及数据库系统。起初，数据库系统主要以网状，层次以及关系数据库为主，而其中尤以关系数据库使用最为广泛，随着科学技术的发展，半结构化和结构化数据在应用中的比重越来越大，而这类具有复杂结构的数据通常以树或图结构来描述。近年来，确定图数据管理技术已被很多学者重视，并且在图挖掘、图数据查询与处理等方面都取得了众多的成果。随着图数据查询管理技术研究的发展，与此同时传感器网络、生物信息学以及web服务技术等相关应用的研究也取得了长足的进步，而这些方面的应用由于研究对象本身的性质以及测量和研究手段的局限性使得不确定性在其中普遍的存在，由此可以知道不确定图数据(UncertainG

5、raphData)有着普遍的研究意义和广泛的应用价值。例如不确定蛋白质交互网络、不确定社会关系网络、不确定交通运输网络等都可以用不确定图数据来对其建模和研究。例如在蛋白质交互网络中，可以使用模式匹配查询，通过疾病蛋白质建立的局部蛋白质交互网络模式Q来查询已知疾病PPI网络库，从而确定新型病毒的性质已完成对疾病的治疗。综上所述，研究有效地基于不确定图的模式匹配查询算法具有重要的现实意义。1．1研究背景和意义数据对于不同的应用领域有着不同的存在形式，如在商业管理领域，主要以关系数据为主，这样的数据模式通常可以使用关系数据库在处理，而在科学以及工程领域，比如：生物信息学、

6、社会关系学、计算机科学、互联网等。这些领域中的数据与商业管理中的数据有着本质上的区别，科学与工程中的数据具有很强的结构化特征，一般符合几何结构、拓扑结构等。图无论在数学还是计算机学科中都是很重要的数据结构，它可以．1．万方数据壅a堡盘鲎亟±堂焦迨塞笠!童缝迨很好的表示几个实体之间的相互关联以及实体内部所具有的结构特征。例如，在蛋白质交互网络和基因科学中，由于这些方面的研究主要以研究化合物分子式为主，对于分子式通常可以采用无向带标签图来表示分子式的所有原子的拓扑结构，图中的每个结点表示分子式中的一个原子，原子的不同种类可以用结点标签来表示，而图中的边可以表示分子中两个

7、原子之间的化合键，边的标签表示化合键的类型。而通过图建模后即可以通过相关的查询操作来完成不同的查询要求，例如，通过模式匹配查询可以通过己知的数据库来发现新物质的相关性质。同上，万维网、社会关系网、作者引用网络都能够以图结构来建模。其次，由于人们知识领域及认识的不断扩展，在计算机应用中广泛存在的数据的不确定性已经越来越被人们所重视，成为近年来计算机领域的重要研究方向和热点研究课题[2-51，同时，图存储结构又是计算机中一种重要的存储方式，因此，不确定图数据的查询处理技术的研究对发展计算机应用技术有着长足和深远的意义。下面阐述一些相关的现实应用：(1)在线社会网络。