| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 基于阈值的概率图可达查询 |
| 作者 | 袁野 王国仁 |
| 作者单位 | (医学影像计算教育部重点实验室(东北大学) 沈阳 110004) (东北大学信息科学与工程学院 沈阳 110004) |
| 发表年份 | 2010 |
| 发表月份 | 12期(2219—2228) |
| 文章摘要 | 摘要 图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF网络等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性，而确定图的可达查询不能有效地处理不确定性，因此该文研究用概率语义描述的图可达性查询.具体的，该文使用可能世界概率模型定义不确定图(称为概率图)，基于该模型，研究了基于阈值的概率可达查询(T-PR).首先为避免枚举所有可能世界，给出一个基本算法可精确求解T-PR查询.其次为进一步加速基本算法，给出3种改进方法，它们是不确定事件界、同构图的缩减、基于不相交路径和割集的界.通过合理的组合给出3种方法的合并算法.最后基于真实概率图数据的大量实验验证了该文的设计. 关键词 概率图；可能世界；不确定事件；同构图缩减；路径集；割集 中图法分类号 TP391 DOI号: 10.3724/SP.J.1016.2010.02219 |