摘要
图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF网络等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定图的可达查询不能有效地处理不确定性,因此该文研究用概率语义描述的图可达性查询.具体的,该文使用可能世界概率模型定义不确定图(称为概率图),基于该模型,研究了基于阈值的概率可达查询(T-PR).首先为避免枚举所有可能世界,给出一个基本算法可精确求解T-PR查询.其次为进一步加速基本算法,给出3种改进方法,它们是不确定事件界、同构图的缩减、基于不相交路径和割集的界.通过合理的组合给出3种方法的合并算法.最后基于真实概率图数据的大量实验验证了该文的设计.
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 probabilistic reachability（T-PR）query over an uncertain graph using the possible world semantics（called probabilistic graph）.Firstly,to avoid enumerating all possible worlds,the authors propose a basic algorithm that can exactly compute T-PR query.To further speed up the basic algorithm,they develop three improved approaches,that is,u-event bounds,isomorphic graph reduction,and disjoint path/cut set bounds.Moreover,the authors combine the three improved algorithms into one entire algorithm.Finally,they have verified the effectiveness of the proposed solutions for T-PR queries through extensive experiments on real probabilistic graph datasets.
出处
《计算机学报》
EI
CSCD
北大核心
2010年第12期2219-2228,共10页
Chinese Journal of Computers
基金
国家自然科学基金重点项目(60933001)
国家自然科学基金面上项目(60773221)
国家"八六三"高技术研究发展计划项目基金(2009AA01Z150)资助~~
关键词
概率图
可能世界
不确定事件
同构图缩减
路径集
割集
probabilistic graph
possible world
uncertain event
isomorphic graph reduction
path set
cut set
