| 基于阈值的概率图可达查询 |
| |
| 引用本文： | 袁野,王国仁. 基于阈值的概率图可达查询[J]. 计算机学报, 2010, 33(12). DOI: 10.3724/SP.J.1016.2010.02219 |
| |
| 作者姓名： | 袁野 王国仁 |
| |
| 作者单位： | 医学影像计算教育部重点实验室(东北大学);东北大学信息科学与工程学院; |
| |
| 基金项目： | 国家自然科学基金重点项目，国家自然科学基金面上项目，国家"八六三"高技术研究发展计划项目基金 |
| |
| 摘 要： | 图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF网络等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定图的可达查询不能有效地处理不确定性,因此该文研究用概率语义描述的图可达性查询.具体的,该文使用可能世界概率模型定义不确定图(称为概率图),基于该模型,研究了基于阈值的概率可达查询(T-PR).首先为避免枚举所有可能世界,给出一个基本算法可精确求解T-PR查询.其次为进一步加速基本算法,给出3种改进方法,它们是不确定事件界、同构图的缩减、基于不相交路径和割集的界.通过合理的组合给出3种方法的合并算法.最后基于真实概率图数据的大量实验验证了该文的设计.
|
| 关 键 词： | 概率图 可能世界 不确定事件 同构图缩减 路径集 割集 |
Answering Threshold-Based Reachability Queries Over Probabilistic Graphs |
| |
| YUAN Ye,WANG Guo-Ren. Answering Threshold-Based Reachability Queries Over Probabilistic Graphs[J]. Chinese Journal of Computers, 2010, 33(12). DOI: 10.3724/SP.J.1016.2010.02219 |
| |
| Authors: | YUAN Ye WANG Guo-Ren |
| |
| Affiliation: | YUAN Ye WANG Guo-Ren(Key Laboratory of Medical Image Computing(Northeastern University),Ministry of Education,Shenyang 110004)(College of Information Science and Engineering,Northeastern University,Shenyang 110004) |
| |
| Abstract: | Graph reachability queries are widely used in biological networks,social networks,ontology networks and RDF networks.Meanwhile,data extracted from those applications is inherently uncertain due to noise,incompleteness and inaccuracy,and traditional certain reachability queries cannot effectively express semantics of such uncertain graph data.Therefore,in this paper,the authors study the reachability queries over uncertain graphs under the probabilistic semantics.Specifically,they study a threshold-based pro... |
| |
| Keywords: | probabilistic graph possible world uncertain event isomorphic graph reduction path set cut set |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
