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

数据立方体压缩技术研究

作　者: 陈富强
导　师: 奚建清
学　校: 华南理工大学
专　业: 计算机应用技术
关键词: 数据立方体商覆盖立方体浓缩数据立方体 QC-table 商位索引冰山覆盖立方体
分类号: TP311.13
类　型: 博士论文
年　份: 2010年
下　载: 223次
引　用: 1次
阅　读: 论文下载

内容摘要

随着商业智能技术与决策支持技术的发展,数据仓库的应用越来越广,其数据量也越来越大,对计算资源的要求越来越高。数据立方体是数据仓库中的一种重要的物化视图,它有助于缩短应答查询的时间,但同时也由于其自身的庞大体积而带来了一系列的问题,包括较高的存储成本、较低的管理维护效率等。数据立方体压缩相关技术是近年来的一个热点研究领域。本文研究了现有的多种数据立方体压缩技术,主要有商覆盖立方体、封闭立方体、QC-table、冰山覆盖立方体等,改进了一些已有的生成算法和查询算法,并对已有研究成果较少涉及的存储、索引以及应答多种类型的查询等问题做了研究。主要工作如下:(1)在已有对数据立方体的压缩技术中,商覆盖立方体压缩效率较高,我们的研究针对商覆盖立方体做了较多的工作。为了为相关研究建立良好的理论基础,本文论证了商覆盖立方体的一些基本性质,提出了一些重要的基础概念;基于这些概念与性质,结合对基本表与立方体中的数据的特性的分析,给出了两种新的生成算法;给出了商覆盖立方体应答点查询、范围查询的算法,以及上卷/下掘的算法。提出了针对商覆盖立方体的商位索引技术,这种技术采用位图文件作为索引,索引文件很小,不仅能快速地定位相关上界格,而且依据索引文件本身和维表即可推算出维值,应答一个点查询时,只需读取体积很小的索引文件,以及在数据文件中读取一条记录即可,产生的磁盘I/O次数较少,应答时间较短。文章还研究了对位图索引进行有效压缩的方法,并改进了游程编码方法,进一步压缩值索引文件。文章还研究了对商覆盖立方体的存储策略,包括选择合适的硬件系统结构、合理的分配策略等。(2)本文还研究了其它一些数据立方体压缩技术,包括封闭立方体、冰山覆盖立方体和QC-table。对封闭立方体,我们提出了封闭掩码的概念,并据此将封闭立方体划分为多个子集,通过在应答查询时只遍历部分子集而减少磁盘I/O次数,缩短应答时间。对冰山覆盖立方体,我们重点研究了其应答查询的方法,提出了一些基本概念,论证了一些重要性质,并基于此给出了对某些类型的冰山覆盖立方体的查询算法,以及通用的冰山覆盖立方体查询算法。对QC-table,我们指出了对之进行研究的重要意义,研究了对其作进一步压缩的方法,并给出了相应的查询算法。(3)提出了一种新的对数据立方体进行压缩的技术,这种技术结合了浓缩数据立方体技术和商覆盖立方体技术,在商覆盖立方体中进一步省略了部分元组,从而进一步压缩了数据文件体积,节省了磁盘存储空间,并有效缩短了应答查询所需的时间。文章给出了相关的数据结构和查询算法。文章最后总结了全文的工作,并指出了进一步的研究方向。

全文目录

摘要  6-8
ABSTRACT  8-14
第一章绪论  14-30
  1.1 研究背景  14
  1.2 数据仓库技术概述  14-18
    1.2.1 数据仓库技术的产生  14-15
    1.2.2 数据仓库与其它相关技术的关系  15-16
    1.2.3 数据仓库中数据的获取与组织  16
    1.2.4 已有数据仓库产品介绍  16-18
  1.3 数据立方体技术简介  18-22
    1.3.1 数据立方体概述  18-21
    1.3.2 聚集函数的类型  21
    1.3.3 查询的类型  21-22
  1.4 数据立方体技术研究现状  22-26
    1.4.1 压缩技术现状  22-24
    1.4.2 索引技术  24-25
    1.4.3 增量维护算法  25
    1.4.4 磁盘存储  25-26
    1.4.5 生成算法  26
  1.5 本文研究内容和创新点  26-28
  1.6 本文的组织  28-30
第二章商覆盖立方体技术  30-62
  2.1 商覆盖立方体概述  30-33
  2.2 维属性顺序选择对DFS 算法效率的影响  33-36
    2.2.1 DFS 算法原理分析  33-35
    2.2.2 实验结果与分析  35-36
  2.3 一种新的商覆盖立方体生成算法  36-39
    2.3.1 基本概念  36-37
    2.3.2 基本性质  37-38
    2.3.3 GroupDFS 算法  38
    2.3.4 实验结果与分析  38-39
  2.4 基本表中的函数依赖对商覆盖立方体生成效率的影响  39-43
    2.4.1 基本表维属性之间的函数依赖  39-41
    2.4.2 对BUC 算法和DFS 算法的分析  41
    2.4.3 概念与定理  41-42
    2.4.4 改进DFS 算法  42-43
    2.4.5 实验结果与分析  43
  2.5 商覆盖立方体的查询算法  43-51
    2.5.1 点查询  43-46
    2.5.2 范围查询  46-47
    2.5.3 下掘算法  47-50
    2.5.4 上卷算法  50-51
  2.6 压缩商覆盖立方体的值索引文件  51-54
    2.6.1 对原有方法可改进之处的分析  51
    2.6.2 对原有方法的改进措施  51-53
    2.6.3 实验结果与分析  53-54
  2.7 商覆盖立方体的磁盘存储策略  54-61
    2.7.1 商覆盖立方体中上界格的热量  54-57
    2.7.2 商覆盖立方体的并行存储策略  57-60
    2.7.3 基于热量均衡的磁盘存储策略  60-61
  2.8 本章小结  61-62
第三章商位索引与序键商立方体  62-75
  3.1 相关研究现状  62-63
  3.2 研究思路  63
  3.3 基本概念及相关性质  63-67
  3.4 商位索引  67-70
    3.4.1 商位索引的概念  67-68
    3.4.2 查找代价分析  68
    3.4.3 商位索引的生成  68-69
    3.4.4 商位索引的适应范围  69
    3.4.5 重新生成的算法  69-70
  3.5 序键商立方体  70
  3.6 实验分析  70-74
  3.7 结论和进一步的工作  74-75
第四章采用掩码文件的封闭立方体查询算法  75-82
  4.1 基本概念  75-76
  4.2 查询算法  76-77
  4.3 封闭掩码集的生成  77-78
  4.4 以二进制位图文件表示掩码  78-79
  4.5 实验结果与分析  79-82
第五章冰山覆盖立方体技术  82-92
  5.1 冰山覆盖立方体简介  82-84
  5.2 问题的提出  84-85
  5.3 采用单调聚集函数的冰山覆盖立方体查询算法  85-88
    5.3.1 偏序关系分析  85
    5.3.2 点查询算法  85-87
    5.3.3 范围查询  87
    5.3.4 查找代价分析  87-88
  5.4 冰山覆盖立方体的通用点查询算法  88-89
  5.5 冰山覆盖立方体的生成算法  89-91
    5.5.1 生成算法  89-91
    5.5.2 实验结果与分析  91
  5.6 下一步的工作  91-92
第六章浓缩商覆盖立方体技术  92-100
  6.1 浓缩商覆盖立方体的概念  92-94
  6.2 相关数据结构  94-96
  6.3 采用浓缩商覆盖立方体应答查询  96-97
    6.3.1 应答点查询  96-97
    6.3.2 应答范围查询  97
  6.4 实验结果与分析  97-99
  6.5 本章结论及进一步工作  99-100
第七章 QC-table 技术  100-110
  7.1 QC-Table 的压缩  100-101
  7.2 压缩 QC-table 的算法  101-103
  7.3 QC-table 应答点查询  103-104
    7.3.1 查询算法  103
    7.3.2 查找代价分析  103-104
    7.3.3 实验结果与分析  104
  7.4 QC-table 应答 Top-k 查询  104-109
    7.4.1 几种格式的数据立方体对Top-k 查询的支持  106-107
    7.4.2 在QC-table 中进行Top-k 查询  107-109
  7.5 结论与进一步的工作  109-110
第八章数据仓库原型系统中相关模块的设计  110-113
  8.1 HDW 系统整体结构  110-111
  8.2 新增功能说明  111-112
    8.2.1 预计算模块  111-112
    8.2.2 XODBC 模块  112
    8.2.3 DCSTORE 模块的设计  112
  8.3 小结  112-113
总结与展望  113-115
参考文献  115-123
攻读博士学位期间取得的研究成果  123-125
致谢  125

数据立方体压缩技术研究

内容摘要

全文目录

相似论文