面向不确定图的概率可达查询

Answering Probabilistic Reachability Queries over Uncertain Graphs

图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF数据库和XML数据库等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,已经有大量的针对不确定RDF和XML数据库的研究.文中使用可能世界语义模型构建不确定图,基于该模型,研究了概率可达查询(PR).处理PR查询是#P完全问题,对此文中首先给出一个基本随机算法,可快速地估算出可达概率,并且该值有很高的精确度.进一步,文中为随机算法引入条件分布(称为"条件随机算法"),采用图的不相交路径集和割集作为条件概率分布,因此改进的随机算法可准确地并且是在多项式时间内处理查询.最后基于真实不确定图数据的大量实验结果验证了文中的设计.

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 processing PR query is a P-complete problem.The authors first propose a basic random algorithm to efficiently estimate the reachable probability with a high quality.To further improve the basic method,the authors introduce conditional distribution in random algorithm called conditional random algorithm（CRA）,and compute the disjoint path set and cut set probabilities for the conditional distribution that is used in CRA,which helps us to find the querying results in polynomial time.Finally,the authors have verified the effectiveness of the proposed solutions for PR queries through extensive experiments on real uncertain graph datasets.