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

被引：10

作者：

袁野 ^{[1
,2
]}

王国仁 ^{[1
,2
]}

机构：

[1] 医学影像计算教育部重点实验室(东北大学)

[2] 东北大学信息科学与工程学院

来源：

计算机学报 | 2010年 / 33卷 / 08期

基金：

国家自然科学基金重点项目;

关键词：

不确定图; 可能世界; 条件随机算法; 路径集; 割集;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

070104 ;

摘要：

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

引用

页码：1378 / 1386

页数：9

共 4 条

[1] 从不确定图中挖掘频繁子图模式 [J].

邹兆年 ;

李建中 ;

高宏 ;

张硕 .

软件学报, 2009, 20 (11) :2965-2976

[2] 不确定图数据库中高效查询处理 [J].

张硕 ;

高宏 ;

李建中 ;

邹兆年 .

计算机学报, 2009, 32 (10) :2066-2079

[3]

Efficient management of transitive relationships in large data and knowledge bases[J] . R. Agrawal,A. Borgida,H. V. Jagadish.ACM SIGMOD Record . 1989 (2)

[4]

Martin Haugh .2 http://www.columbia.edu/mh2078/MCS04.ht ml .

← 1 →