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

作     者：袁野 王国仁 YUAN Ye;WANG Guo-Ren

作者机构：医学影像计算教育部重点实验室(东北大学)沈阳110004 东北大学信息科学与工程学院沈阳110004 

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

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2010年第33卷第8期

页      码：1378-1386页

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

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

学科分类：08[工学] 0835[0835] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3724/SP.J.1016.2010.01378

馆 藏 号：203948964...