基于阈值的概率图可达查询

摘要：

图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF网络等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定图的可达查询不能有效地处理不确定性,因此该文研究用概率语义描述的图可达性查询.具体的,该文使用可能世界概率模型定义不确定图(称为概率图),基于该模型,研究了基于阈值的概率可达查询(T-PR).首先为避免枚举所有可能世界,给出一个基本算法可精确求解T-PR查询.其次为进一步加速基本算法,给出3种改进方法,它们是不确定事件界、同构图的缩减、基于不相交路径和割集的界.通过合理的组合给出3种方法的合并算法.最后基于真实概率图数据的大量实验验证了该文的设计.

关键词：概率图、可能世界、不确定事件、同构图缩减、路径集、割集

所属期刊栏目：33

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金重点项目60933001;国家自然科学基金面上项目60773221;国家"八六三"高技术研究发展计划项目基金2009AA01Z150

在线出版日期：2011-03-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：2219-2228