条件概率图数据管理关键技术研究

图是一种通用的数据结构，已应用到科学与工程的各个领域，如计算化学、生物信息学、流体动力学、社会关系学等。而现代科学的研究方法和测量技术普遍存在误差和噪声，使获取的图数据具有不确定性，例如不确定社会关系网络、不确定道路交通网络、不确定蛋白质交互网络等，促使不确定图数据管理技术的研究已逐渐成为当前数据库领域的研究热点之一。然而现有的针对不确定图数据管理的研究工作寥寥无几，主要集中在不确定图的可达查询和频繁子图挖掘。并且图模型假设概率独立，此假设过于严格，不符合实际的需求。为此本项目紧紧围绕条件概率图数据管理的关键技术展开深入研究，力争在条件概率图数据模型、存储与索引、复杂查询处理等方面取得原创性的突破成果，并通过构建条件概率图数据管理原型系统来验证这些研究成果的有效性。相关研究成果将为条件概率图数据的管理提供新的解决方案，进一步拓宽条件概率图数据的应用范围，具有重要的理论意义与实际应用价值。

本项目的执行时间是2011.1——2014.12，这期间项目主要研究了条件概率图数据管理的各个方面，现总结如下：.1. 在条件概率图数据模型和存储方面，项目组提出了概率独立图模型、基于Markov网络的无向图模型、基于Bayesian网络的有向图模型；并提出通用的概率邻接链表存储结构、概率邻接矩阵存储结构。.2. 在条件概率图数据查询处理方面，项目组提出了统一的查询处理框架，它可高效地处理百万个数不确定图数据的包含图查询、磁盘驻留不确定图数据的关键字查询、超大规模单一不确定图的可达查询等。该框架可同时无缝地集成项目组研发的高效图索引：概率路径树索引、基于频繁子图的索引、概率相似矩阵索引、基于Junction Tree的索引。 .3. 在条件概率图数据分析方面，项目组提出了无偏而低误差的通用采样算法，它可高效地处理大规模不确定图数据的聚类和分类、高效地挖掘千万结点大图的频繁子图和区分子图、高效地监控不确定图数据流的异常点。.4. 本项目实施过程中，项目组已在VLDB Journal、IEEE TKDE、VLDB等国际权威期刊和国际会议上发表论文30篇，其中SCI期刊发表论文13篇，其中的论文获得辽宁省自然科学学术成果一等奖。培养毕业研究生5名，项目成员的博士论文《不确定图数据的查询处理技术研究》获得2012年中国计算机学会（CCF）优秀博士论文奖和2013年全国优秀博士论文提名奖。开发的条件概率图数据管理原型系统已经得到应用，并申请国家发明专利2项。关于概率图数据查询处理的一系列算法是本课题成员在国际上率先提出来的，奠定了我国在不确定图数据管理研究领域的国际领先地位。