| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 面向不确定图的概率可达查询 |
| 作者 | 袁野1),2) 王国仁1),2) |
| 作者单位 | 1)(医学影像计算教育部重点实验室(东北大学) 沈阳 110004) 2)(东北大学信息科学与工程学院 沈阳 110004) |
| 发表年份 | 2010 |
| 发表月份 | 8期(1378—1386) |
| 文章摘要 | 摘要 图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF数据库和XML数据库等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性，已经有大量的针对不确定RDF和XML数据库的研究.文中使用可能世界语义模型构建不确定图，基于该模型，研究了概率可达查询(PR).处理PR查询是#P完全问题，对此文中首先给出一个基本随机算法，可快速地估算出可达概率，并且该值有很高的精确度.进一步，文中为随机算法引入条件分布(称为“条件随机算法”)，采用图的不相交路径集和割集作为条件概率分布，因此改进的随机算法可准确地并且是在多项式时间内处理查询.最后基于真实不确定图数据的大量实验结果验证了文中的设计. 关键词 不确定图；可能世界；条件随机算法；路径集；割集 中图法分类号 TP311 DOI号：10.3724/SP.J.1016.2010.01378 |