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

摘要：

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

关键词：不确定图、可能世界、条件随机算法、路径集、割集

所属期刊栏目：33

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金重点项目60933001;国家自然科学基金面上项目60773221;国家"八六三"高技术研究发展计划项目基金2009AA01Z150;国家自然科学基金60803026

在线出版日期：2010-10-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1378-1386