| 面向不确定图的概率可达查询 |
| |
| 引用本文： | 袁野,王国仁.面向不确定图的概率可达查询[J].计算机学报,2010,33(8). |
| |
| 作者姓名： | 袁野 王国仁 |
| |
| 作者单位： | 医学影像计算教育部重点实验室(东北大学)沈阳,110004;东北大学信息科学与工程学院,沈阳,110004 |
| |
| 基金项目： | 国家自然科学基金重点项目，国家自然科学基金面上项目，国家"八六三"高技术研究发展计划项目基金，国家自然科学基金 |
| |
| 摘 要： | 图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF数据库和XML数据库等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,已经有大量的针对不确定RDF和XML数据库的研究.文中使用可能世界语义模型构建不确定图,基于该模型,研究了概率可达查询(PR).处理PR查询是#P完全问题,对此文中首先给出一个基本随机算法,可快速地估算出可达概率,并且该值有很高的精确度.进一步,文中为随机算法引入条件分布(称为"条件随机算法"),采用图的不相交路径集和割集作为条件概率分布,因此改进的随机算法可准确地并且是在多项式时间内处理查询.最后基于真实不确定图数据的大量实验结果验证了文中的设计.
|
| 关 键 词： | 不确定图 可能世界 条件随机算法 路径集 割集 |
Answering Probabilistic Reachability Queries over Uncertain Graphs |
| |
| YUAN Ye,WANG Guo-Ren.Answering Probabilistic Reachability Queries over Uncertain Graphs[J].Chinese Journal of Computers,2010,33(8). |
| |
| Authors: | YUAN Ye WANG Guo-Ren |
| |
| Affiliation: | YUAN Ye1),2) WANG Guo-Ren1),2)1)(Key Laboratory of Medical Image Computing(Northeastern University),Ministry of Education,Shenyang 110004)2)(College of Information Science and Engineering,Northeastern University,Shenyang 110004) |
| |
| Abstract: | Graph reachability queries are widely used in biological networks,social networks,ontology networks,RDF and XML databases.Meanwhile,data extracted from those applications is inherently uncertain due to noise,incompleteness and inaccuracy,and many works have been proposed to study uncertain RDF and XML databases.This paper discusses the reachability queries over uncertain graphs,specifically a probabilistic reachability(PR) query over an uncertain graph using the possible world semantics.It is proved that pr... |
| |
| Keywords: | uncertain graph possible world conditional random algorithm path set cut set |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
