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

基于概率数据库的偏好查询研究

作 者: 王晓伟
导 师: 贾焰
学 校: 国防科学技术大学
专 业: 计算机科学与技术
关键词: 不确定数据 概率数据库 偏好查询 top-k skyline
分类号: TP311.13
类 型: 博士论文
年 份: 2011年
下 载: 34次
引 用: 0次
阅 读: 论文下载
 

内容摘要


在商业数据管理、金融数据分析、传感器、RFID、地理信息系统等许多重要的现代应用中,数据普遍带有不确定性特征,查询和分析的精确度对应用是否成功具有决定性影响。传统的数据库技术建立在确定性理论的基础上,无法有效处理此类不确定数据概率数据库技术能够直接管理不确定数据,是近年来数据库领域的研究热点。概率数据库的应用层通过偏好查询满足用户的个性需求,其中最重要的偏好查询是概率skyline和概率top-k查询。本文针对基于概率数据库的偏好查询技术,从提高查询效率和通用性出发,对概率skyline查询和概率top-k查询的若干关键问题展开研究,主要工作包括:1、概率skyline查询的非索引算法。现有的概率skyline算法普遍基于R树索引,而R树索引技术在通用性方面存在限制。非索引算法不需要任何预处理或索引结构,具有最广泛的适用性,是索引算法的必要补充。基本思想是从已访问的对象中提取概率信息,来估计未来访问对象的skyline概率。分别提出了基于内存R树和有序链表的两种非索引算法。实验结果表明,两种算法均明显优于朴素的非索引算法,且在对数据维度的适应性方面互为补充。2、概率skyline查询的分布式算法。现实应用中,数据通常分散于多个分布节点,分布式概率skyline查询的延迟主要取决于通信开销。以降低通信开销为主要目标,提出了基于概要共享的分布式概率skyline算法框架,然后分别提出了两种具体算法。其中,VOS算法将虚对象集合作为间接表示数据分布的概要,用基于距离的虚对象集合压缩方法来降低共享虚对象导致的额外通信开销;GRID算法着眼于克服VOS算法对数据分布的依赖性,将对象映射到固定宽度的网格中,提出网格概要的压缩方法来减少共享网格带来的额外通信开销。实验结果表明,VOS和GRID均优于现有算法。其中前者适于处理具有独立分布特征或维度较高的数据,后者更适合处理具有反相关特征的数据。3、支持多种概率top-k查询的层次索引。概率top-k查询需要同时考虑评分函数值和存在概率值,因此具有不同语义。每种语义都有专门的查询处理方法,缺少能应用于一类重要语义的索引技术。提出两种层次索引,能应用于满足特定性质的一类概率top-k查询。首先提出基于skyline的SL索引,为了提高SL索引的鲁棒性,进一步提出了基于支配频率的FL索引,并提出了高效的索引建立算法。实验结果表明,SL索引和FL索引均能显著减少需要访问的对象数量,其中FL索引具有更好的鲁棒性。4、概率逆top-k查询。前述研究成果都是从用户角度出发的查询优化问题,逆top-k查询能够帮助生产者分析产品影响的用户群体,在商业分析等领域有重要应用。现有逆top-k算法针对确定数据,在现实应用中,数据往往由于数据集成等原因带有不确定性。提出了概率逆top-k查询的合理定义,并提出了基于物化视图的查询算法。该算法将数据空间划分为网格,预先计算网格顶点的查询结果,后续查询利用物化视图避免对偏好集合的全盘访问。实验结果表明,基于物化视图的查询算法能够有效减少需要计算的偏好数量。综上所述,本文针对基于概率数据库的两类偏好查询,提出了较为高效和通用的的解决方法,对于概率数据库的研究和应用具有一定的理论意义和应用价值。

全文目录


摘要  11-13
Abstract  13-15
第一章 绪论  15-37
  1.1 研究背景  15-24
    1.1.1 应用背景  15-17
    1.1.2 相关概念与技术  17-24
  1.2 相关工作  24-32
    1.2.1 不确定数据  24-25
    1.2.2 概率数据管理  25-28
    1.2.3 不确定数据挖掘  28-29
    1.2.4 偏好查询  29-31
    1.2.5 研究现状总结  31-32
  1.3 本文工作与创新点  32-34
    1.3.1 研究内容  32-33
    1.3.2 主要创新点  33-34
  1.4 论文结构  34-37
第二章 概率 Skyline 查询的非索引算法  37-63
  2.1 研究背景  37-39
  2.2 相关工作  39-40
    2.2.1 确定 Skyline 的非索引算法  39
    2.2.2 概率 Skyline 算法  39-40
  2.3 基本算法  40-41
  2.4 基于虚对象的算法  41-54
    2.4.1 基本思想  41-42
    2.4.2 具体算法  42-46
    2.4.3 虚对象集合的组织与维护  46-52
    2.4.4 算法分析  52-54
  2.5 实验  54-61
    2.5.1 实验设置  54-55
    2.5.2 实验结果  55-61
    2.5.3 实验结论  61
  2.6 本章小结  61-63
第三章 分布式概率 Skyline 查询  63-83
  3.1 问题分析  63-65
    3.1.1 问题描述  63-64
    3.1.2 概率 Skyline 的不可分解性  64-65
  3.2 相关工作  65-67
    3.2.1 分布式确定 Skyline  65-66
    3.2.2 分布式概率 Skyline  66-67
  3.3 基于概要共享的算法框架  67-68
    3.3.1 核心思想  67
    3.3.2 算法框架  67-68
  3.4 基于虚对象的算法  68-73
    3.4.1 基本思想  68-69
    3.4.2 压缩虚对象集合  69-70
    3.4.3 虚对象集合的生成和合并算法  70-72
    3.4.4 算法分析  72-73
  3.5 基于网格划分的算法  73-78
    3.5.1 网格概要  73-74
    3.5.2 合并网格概要  74
    3.5.3 基于网格概要的裁剪算法  74-76
    3.5.4 压缩网格概要  76-78
    3.5.5 算法分析  78
  3.6 实验  78-81
    3.6.1 实验设置  78
    3.6.2 实验结果  78-81
    3.6.3 实验结论  81
  3.7 本章小结  81-83
第四章 支持多种概率 Top-k 查询的层次索引  83-99
  4.1 问题分析  83-84
  4.2 相关工作  84-86
    4.2.1 概率 Top-k 查询  84-85
    4.2.2 不确定数据上的索引技术  85
    4.2.3 确定数据上 Top-k 索引  85-86
  4.3 基于 Skyline 的层次索引  86-90
    4.3.1 SL 索引  87-88
    4.3.2 基于 SL 索引的概率 Top-k 查询  88-89
    4.3.3 建立 SL 索引  89-90
  4.4 基于支配频率的层次索引  90-94
    4.4.1 FL 索引  90-91
    4.4.2 鲁棒性分析  91-92
    4.4.3 建立 FL 索引  92-94
  4.5 实验  94-96
    4.5.1 实验设置  94
    4.5.2 实验结果  94-96
    4.5.3 实验结论  96
  4.6 本章小结  96-99
第五章 概率逆 Top-k 查询  99-111
  5.1 研究背景  99-100
  5.2 问题定义  100-102
  5.3 相关工作  102-103
  5.4 基本算法  103-104
  5.5 基于物化视图的改进算法  104-106
    5.5.1 基于物化视图的查询算法  104-106
    5.5.2 生成基于网格的物化视图  106
  5.6 其他语义及处理方法  106-107
  5.7 实验  107-109
    5.7.1 实验设置  107
    5.7.2 实验结果  107-109
  5.8 本章小结  109-111
第六章 结论与展望  111-113
  6.1 工作总结  111-112
  6.2 工作展望  112-113
致谢  113-115
参考文献  115-127
作者在学期间取得的学术成果  127-129
攻读博士学位期间参加的科研项目  129

相似论文

  1. 支持Top-k查询的银行记账查询系统的设计与实现,TP311.52
  2. 基于不确定数据的轮廓查询处理技术研究,TP311.13
  3. 海量数据的快速查询算法研究,TP311.13
  4. 不确定时间序列的相似性匹配问题研究,TP311.13
  5. 不确定数据的概率Skyline查询算法研究,TP311.13
  6. K-匿名数据的查询方法研究,TP309
  7. 云计算环境下的容错并行Skyline查询技术研究,TP311.13
  8. 基于三维的机械系统Top-down设计关键技术,TH122
  9. 基于Skyline的农业资源三维地理信息系统框架设计与实现,F320.1
  10. 基于ArcGIS Server的旅游地理信息系统研究,P208
  11. 基于ArcGIS Engine和Skyline的黄壁庄水库地理信息系统研究,P208
  12. 隧道挖装机挖掘装置的参数化设计研究,U455.3
  13. 沥青路面近荷载区Top-Down裂缝形成机理及扩展规律分析,U416.217
  14. SAAS模式在TOP上的研究与实现,TP393.09
  15. 面向移动对象的连续概率Skyline查询的研究,TP311.13
  16. 基于Skyline的世博可视化系统关键技术的研究和实现,TP391.41
  17. 数字乡村三维可视化系统的设计与实现,P208
  18. 不确定数据流上Skyline查询处理技术研究,TP311.13
  19. 三维警卫地理信息系统,P208
  20. 基于Skyline的Web三维GIS应用研究,P208
  21. 无线传感器网络中Top-k查询处理技术的研究,TN929.5

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com