学位论文 > 优秀研究生学位论文题录展示

关于不确定性数据置信度算法的研究

作　者: 刘光熠
导　师: 张亮
学　校: 复旦大学
专　业: 计算机软件与理论
关键词: 不确定性数据世系置信度世系图独立模块事故树最小割集
分类号: TP311.13
类　型: 硕士论文
年　份: 2010年
下　载: 63次
引　用: 0次
阅　读: 论文下载

内容摘要

近几十年来,传统的确定性数据(deterministic data)管理技术得到了迅猛的发展,在国民经济建设中起到了突出作用。在传统数据库的应用中,数据的存在性和精确性均确凿无疑[1]。近年来,随着技术的进步和人们对数据采集和处理技术理解的不断深入,不确定性数据(uncertain data)[8][25][26]得到广泛的重视。数据整合、数据抽取、科学数据管理、多媒体应用以及知识学习等应用都有充斥着非确定性数据。传统的数据管理技术却无法有效管理不确定性数据,这就引发了学术界和工业界对研发新型的不确定性数据管理技术的兴趣。目前,已经国际上已经提出了几种非确定性数据库模型,其中最为典型的是斯坦福大学的ULDBs[6]模型。ULDBs基于可能世界模型,扩展了关系数据库模型,提出了相对统一的处理和描述非确定性数据的标准,其TRIO[7][28]系统也较为成熟。但由于庞大的可能世界实例集合和概率维的存在,目前基于ULDBs的数据查询还是个难点,尤其是结果数据置信度的计算。例如,如果某不确定性数据库含N条元组,各元组独立。当该数据库仅有存在级不确定性,可能世界的数目将达到2N个。如果查询要求访问所有的可能世界时,则这个查询开销将会是一个#P问题[19][24]。本文基于ULDBs模型,提出了一种置信度改进算法,能有效地减少不确定性数据查询的时间。本文首先概述了非确定性数据库的研究的背景和相关研究现状和研究意义,总结了扩展关系数据库系统处理非确定性数据的挑战。然后详细介绍了带世系分析的非确定性数据库模型ULDBs,描述了ULDBs如何表示不确定性数据,介绍了数据世系的概念及其与不确定性数据的结合,并介绍了如何把概率扩展到ULDBs。在分析ULDBs非确定性数据库模型后,本文重点研究了基于ULBDs的数据查询。研究了针对各种关系操作,如何计算其结果数据和数据世系。然后分析了Widom的置信度算法和独立模块求解算法,并分析了其优点和不足。在分析和借鉴的基础上,提出了一个基于深度优先最左遍历的独立模块求解算法,并就时间复杂度对本文算法和Widom的算法进行了比较。经比较发现,本文算法在数据世系中节点数目较多时,有更高的效率。本文的主要研究成果包括：提出了一种基于深度优先最左遍历的独立模块求解算法,将原算法的时间复杂度从O(N*E)降到了O(N*H)(其中M代表世系图中节点的个数,E代表边数,H代表节点的平均祖先节点数目)；针对较为复杂的独立模块,提出了一种基于最小割集的置信度算法,将原算法的复杂度从O(2k)降到了O(S)(其中k为独立模块中基础元组的个数,S为其最小割集的数目,S≤2k),减少了计算量；通过实验并和其他相关工作进行比较,说明本解决方案的实用性。

全文目录

目录  3-5
摘要  5-6
Abstract  6-8
第一章引言  8-13
  1.1 研究的目的和意义  8-9
  1.2 国内外研究状况  9-11
  1.3 本文工作  11-12
  1.4 论文的组织结构  12-13
第二章不确定性数据的建模  13-22
  2.1 可能世界模型  13-14
  2.2 带世系分析的不确定性数据库(ULDBs)  14-18
    2.2.1 带数据世系的数据库(LDBs)  14-15
    2.2.2 非确定性数据库(UDBs)  15-16
    2.2.3 结合非确定性和数据世系  16-18
  2.3 扩展的ULDBs  18-21
    2.3.1 置信度  19
    2.3.2 查询处理  19-21
  2.4 本章小结  21-22
第三章不确定性数据的查询  22-41
  3.1 不确定性数据的计算  22-25
    3.1.1 关系操作和查询方案  23-25
  3.2 置信度的计算  25-32
    3.2.1 一个基础的算法  25-27
    3.2.2 Widom的改进算法  27-32
  3.3 算法改进  32-39
    3.3.1 一个寻找独立模块的改进算法  32-36
    3.3.2 对Eval(f,c_1,c_2,...,c_k)算法的改进  36-39
  3.4 算法的比较  39-40
  3.5 本章小结  40-41
第四章实验和评估  41-48
  4.1 实验数据集  41
  4.2 实验设计  41
  4.3 实验结果和分析  41-48
    4.3.1 利用独立模块的效果:NaiveConf()算法Vs IndepConf()算法  41-44
    4.3.2 独立模块求解:DMLFIndep()算法Vs Indep()算法  44-46
    4.3.3 独立模块置信度求解:真值表法Vs基于最小割集的算法  46-47
    4.3.4 本章小结  47-48
第五章总结和展望  48-50
  5.1 总结  48
  5.2 进一步工作  48-50
附录一硕士期间所发表的论文  50-51
参考文献  51-54
致谢  54-55

关于不确定性数据置信度算法的研究

内容摘要

全文目录

相似论文