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

数据仓库环境中近似查询处理技术研究

作　者: 冯玉
导　师: 王珊
学　校: 中国科学院研究生院（计算技术研究所）
专　业: 计算机应用技术
关键词: 数据仓库近似查询处理聚类分析数据方体数据压缩
分类号: TP311.13
类　型: 博士论文
年　份: 2002年
下　载: 418次
引　用: 3次
阅　读: 论文下载

内容摘要

在数据仓库上的许多决策支持应用需要在大数据量上进行复杂的查询,由于大数据量以及查询的复杂性使得一个查询的执行通常需要很长时间,显然不能满足用户的需求,有时为了提高系统的响应时间,用户可以容忍一些查询结果的精度,因此近似查询处理技术成为有效解决这一问题的方法。数据仓库环境中的许多应用模式都对近似查询技术提出需求。例如,我们在做OLAP分析时,在一个钻取(drill-down)查询序列中,最初查询的目的就是为了决定我们真正感兴趣的数据,给这些查询提供快速、近似的查询结果可以使用户尽快找到有用的数据。在数据仓库上的许多决策支持应用中的查询目的着重于分析数据间的关联关系或发展趋势,有时在做聚集集查询时,对查询结果的要求并不需要精确到小数点。本文主要研究在数据仓库环境中的近似查询处理技术,根据数据仓库中数据和OLAP查询的特点,提出了基于聚类技术的近似查询处理方法(Cluster-based Approximate Query Processing method,简记为CAQP),其主要思想是对数据仓库中数据方体的数据进行分块,每块数据相当于多维空间中的一个点,采用聚类技术对数据方体中的这些数据块聚类,对于每个cluster,使用其中心点的值代表其中所有的数据块,对数据方体进行压缩,以后的查询操作则直接在压缩的数据结构上进行,减少查询处理时的I/O开销,从而提高查询性能。本文首先对聚类技术进行了深入的研究,提出了基于方格和密度的新聚类算法SCARG,它的基本思想是把整个数据空间划分成矩形区域,如果一个区域的密度大于一个阀值,则该区域是一个密集区域,把所有相关联的密集区域连接起来,构成一个Cluster。本文采用移动中心点的技术,对聚类结果进一步细化,提高聚类的精度。SCARG算法兼具了基于方格算法的处理速度和基于密度方法处理任意形状cluster的能力。本文还通过人工合成数据和Benchmark数据进行实验,与其它著名的聚类算法(DBSCAN,CLARANS)对比,验证了SCARG算法的有效性和性能。同时,本文还给出了SCARG算法的并行版本PSCARG,该算法充分利用硬件资源,进一步提高了对海量数据的处理能力。本文在深入研究了聚类技术的基础上,又对基于聚类的近似查询处理的关键技术进行研究,即对于数据仓库中的数据,如何采用聚类技术进行近似查询处理,主要包括数据的预处理、聚类的分层计算以及数据的增量维护算法等。针对数据仓库上的常用操作,本文设计了数据的存储结构,给出了在数据方体压缩结构上进行查询处理的算法,并给出了对查询结果集置信区间的估算方法,并通过实验与抽样技术对比,说明了CAQP方法的有效性和可扩展性。本文对近似扩展数据方体技术进行了研究。近似扩展数据方体是由2n-1个子方体组

全文目录

独创性声明  3
关于论文使用授权的说明  3-4
摘要  4-6
ABSTRACT  6-11
第一章引言  11-19
  1.1 数据仓库技术的产生与发展  11-13
  1.2 近似查询处理技术的研究背景与意义  13-14
  1.3 近似查询处理技术的国内外研究状况  14-16
  1.4 论文的主要工作  16-17
  1.5 论文的组织安排  17-19
第二章数据仓库与近似查询技术的相关研究  19-37
  2.1 数据仓库技术  19-22
    2.1.1 实体化视图  19-20
    2.1.2 索引  20
    2.1.3 数据方体（data cube）技术  20-21
    2.1.4 并行处理技术  21
    2.1.5 数据压缩技术  21-22
  2.2 近似查询处理的基本概念  22-23
  2.3 聚集查询近似处理技术研究  23-29
    2.3.1 抽样技术  24-25
    2.3.2 直方图技术（Histogram）  25-27
    2.3.3 小波变换技术（Wavelet）  27-28
    2.3.4 其它技术  28-29
  2.4 非聚集查询的近似处理技术研究  29-30
  2.5 数据压缩技术  30-32
  2.6 近似查询结果评价  32-34
  2.7 小结  34-37
第三章基于聚类的近似查询处理方法概述  37-49
  3.1 数据仓库中的数据模型  37-42
    3.1.1 多维数据模型  37-40
    3.1.2 多维数据模型的物理实现  40-41
    3.1.30 LAP 的基本操作  41-42
  3.2 并行数据仓库系统ParaWare 概述  42-43
    3.2.1 ParaWare 的体系结构  42-43
    3.2.2 ParaWare 的数据模型  43
  3.3 CAQP 的基本结构  43-46
    3.3.1 数据预处理模块  44
    3.3.2 数据存储模块  44-45
    3.3.3 聚类模块  45
    3.3.4 数据维护模块  45
    3.3.5 查询处理模块  45
    3.3.6 近似扩展数据方体模块  45-46
  3.4 CAQP 与ParaWare 的关系  46
  3.5 CAQP 的特点  46-47
  3.6 小结  47-49
第四章聚类分析技术研究  49-69
  4.1 聚类分析概述  49-50
  4.2 聚类分析的相关研究  50-56
    4.2.1 基于分区的聚类方法  50-53
    4.2.2 基于层次的聚类方法  53-54
    4.2.3 基于密度的聚类方法  54-55
    4.2.4 基于方格的聚类方法  55
    4.2.5 基于模型的聚类方法  55-56
    4.2.6 聚类方法小结  56
  4.3 SCARG 方法  56-65
    4.3.1 问题说明  56-57
    4.3.2 SCARG 算法的关键技术  57-59
    4.3.3 SCARG 算法  59-61
    4.3.4 算法分析  61
    4.3.5 实验  61-65
    4.3.6 SCARG 算法小结  65
  4.4 PSCARG 方法  65-68
    4.4.1 PSCARG 算法说明  66-67
    4.4.2 实验  67-68
  4.5 小结  68-69
第五章基于聚类的近似查询处理关键技术  69-87
  5.1 近似查询处理的有关定义  69-70
  5.2 数据的预处理  70-72
    5.2.1 数据方体的划分  70-71
    5.2.2 数据的生成算法  71-72
  5.3 数据的存储结构  72-75
    5.3.1 数据结构  72-73
    5.3.2 霍夫曼编码  73-75
  5.4 聚类的计算  75-78
    5.4.1 分层K-Means 方法  76-77
    5.4.25 CARG 与K-Means 相结合的算法  77-78
  5.5 数据的维护  78-79
  5.6 查询处理  79-81
  5.7 查询结果的估计值和置信区间  81-83
    5.7.1 非聚集查询  82
    5.7.2 聚集查询  82-83
  5.8 实验  83-85
    5.8.1 数据描述  83
    5.8.2 实验方法  83
    5.8.3 算法的准确性  83-84
    5.8.4 算法的扩展性  84-85
  5.9 小结  85-87
第六章近似扩展数据方体技术  87-97
  6.1 近似扩展数据方体概述  87
  6.2 近似扩展数据方体的计算  87-89
  6.3 近似扩展数据方体的配置  89-95
    6.3.1 集合覆盖问题  90-91
    6.3.2 启发式算法  91-95
  6.4 近似扩展数据方体的维护  95
  6.5 近似扩展数据方体的查询优化  95
  6.6 小结  95-97
第七章总结与展望  97-101
  7.1 本文的主要贡献和创新  97-98
  7.2 进一步的工作  98-101
参考文献  101-109
致谢  109-110
作者简历  110

数据仓库环境中近似查询处理技术研究

内容摘要

全文目录

相似论文