Fully Dynamic Partitioning: Handling Data Skew in Parallel Data Cube Computation

Parallel data processing is a promising approach for efficiently computing data cube in relational databases, because most aggregate functions used in OLAP (On-Line Analytical Processing) are distributive functions. This paper studies the issues of handling data skew in parallel data cube computation. We present a fully dynamic partitioning approach that can effectively distribute workload among processing nodes without priori knowledge of data distribution. As supplement, a simple and effective dynamic load balancing mechanism is also incorporated into our algorithm, which further improves the overall performance. Our experimental results indicated that the proposed techniques are effective even when high data skew exists. The results of scale-up and speedup tests are also satisfactory.     

Star Cube--一种高效的数据立方体实现方法

一个具有n个维的数据立方体有2^n个视图,视图越多,用于维护数据立方体的时间也就越长。通过将维分成划分维和非划分维,数据立方体可以转换成star cube．stal cube由一个综合表和那些仅包含划分维的视图组成。star cube使用前缀共享和元组共享技术不仅减少了所需的存储空间,还大大减少了计算和维护时间。在把一个分片限制在一个I/O单位的条件下,star cube的查询响应时间与数据立方体基本相同。实验结果也表明,star cube是一种在时空两方面均有效的数据立方体实现技术。     

一种应用于OLAP的数据模型及其实现

数据仓库及OLAP技术是当前数据库领域研究的热点,而数据模型又是数据仓库及OLAP核心基础。文章提出了一种应用于OLAP的数据模型,并用于实际应用中。这种数据模型在概念上表达了OLAP特性,支持OLAP操作,而且其数学代数简单明白地表达了OLAP查询。     

基于数据立方体的关联规则挖掘及其实现

联机分析处理和数据挖掘是两种重要的数据分析方法。使用数据立方体作为数据存储结构,将两者集成起来,使得用户可以从不同角度、不同抽象层次分析数据。针对数据立方体的特点,本文提出了挖掘维间关联规则的算法,并编程实现了该算法,取得满意的结果。     

OLAP核心技术-数据立方体的研究现状与展望

该文从OLAP的基本功能出发,综述了其核心技术－数据立方体（Data Cube)的研究现状,主要讨论了3个方面：数据立方体建模,数据立方体计算和数据立方体操作,最后展望了该领域的研究方向。     

Parallel ROLAP Data Cube Construction on Shared-Nothing Multiprocessors

The pre-computation of data cubes is critical to improving the response time of On-Line Analytical Processing (OLAP) systems and can be instrumental in accelerating data mining tasks in large data warehouses. In order to meet the need for improved performance created by growing data sizes, parallel solutions for generating the data cube are becoming increasingly important. This paper presents a parallel method for generating data cubes on a shared-nothing multiprocessor. Since no (expensive) shared disk is required, our method can be used on low cost Beowulf style clusters consisting of standard PCs with local disks connected via a data switch. Our approach uses a ROLAP representation of the data cube where views are stored as relational tables. This allows for tight integration with current relational database technology.We have implemented our parallel shared-nothing data cube generation method and evaluated it on a PC cluster, exploring relative speedup, local vs. global schedule trees, data skew, cardinality of dimensions, data dimensionality, and balance tradeoffs. For an input data set of 2,000,000 rows (72 Megabytes), our parallel data cube generation method achieves close to optimal speedup; generating a full data cube of 227 million rows (5.6 Gigabytes) on a 16 processors cluster in under 6 minutes. For an input data set of 10,000,000 rows (360 Megabytes), our parallel method, running on a 16 processor PC cluster, created a data cube consisting of 846 million rows (21.7 Gigabytes) in under 47 minutes.     

Optimization in Data Cube System Design

The design of an OLAP system for supporting real-time queries is one of the major research issues. One approach is to use data cubes, which are materialized precomputed multidimensional views of data in a data warehouse. We can derive a set of data cubes to answer each frequently asked query directly. However, there are two practical problems: (1) the maintenance cost of the data cubes, and (2) the query cost to answer those queries. Maintaining a data cube requires disk storage and CPU computation, so the maintenance cost is related to the total size as well as the total number of data cubes materialized. In most cases, materializing all data cubes is impractical. The maintenance cost may be reduced by merging some data cubes. However, the resulting larger data cubes will increase the query cost of answering some queries. If the bounds on the maintenance cost and the query cost are too strict, we help the user decide which queries to be sacrificed and not taken into consideration. We have defined an optimization problem in data cube system design. Given a maintenance-cost bound, a query-cost bound and a set of frequently asked queries, it is necessary to determine a set of data cubes such that the system can answer a largest subset of the queries without violating the two bounds. This is an NP-hard problem. We propose approximate Greedy algorithms GR, 2GM and 2GMM, which are shown to be both effective and efficient by experiments done on a census data set and a forest-cover-type data set.     

基于图形处理器的并行方体计算

方体(cube)计算是数据仓库和联机分析处理(Online analytical processing,OLAP)领域的核心问题,如何提高方体计算性能获得了学术界和工业界的广泛关注,但目前大部分方体算法都没有考虑最新的处理器架构.近年来,处理器从单一计算核心进化为多个或许多个计算核心,如多核CPU、图形处理器(Graphic Processing Units, GPU)等.为了充分利用现代处理器的多核资源,该文提出了基于GPU的并行方体算法GPU-Cubing,算法采用自底向上、广度优先的划分策略,每次并行完成一个cuboid的计算并输出;在计算cuboid过程中多个分区同步处理,分区内多线程并行.GPU-Cubing算法适合GPU体系结构,并行度高.与BUC算法相比,基于真实数据集的完全方体计算可以获得一个数量级以上的加速比,冰山方体获得至少2倍以上的加速.     

基于内存的数据立方查询处理

随着内存容量的飞速扩大,出现了一些配备以GB计的内存的工作站。但现行的OLAP系统都没有充分利用大容量RAM,鉴于此,文章提出一种基于内存的数据立方查询处理系统。该系统采用一种二级索引内存数据结构,充分利用有限的内存空间,有效组织各数据小方的元组,实现了高效数据立方查询。     

GSFC--基于图结构的Free Cube存储方法

free cube利用发掘基本关系表维值之间的蕴含规则,去除data cube中内在冗余,有效减小data cube体积．但是还存在一些值得进一步研究的问题．首先,直接地表示free cube仍然不够精简从而浪费了存储空间．其次,只提到了查询的基本思想,没有给出具体的查询技术．针对这些问题,提出了基于图结构的存储方法GSFC,利用前缀压缩进一步减小free cube体积．同时,该方法结合了存储和索引结构,有效解决free cube的查询问题．最后给出了计算和查询算法,并利用实验来证明算法的有效性．     

数据仓库中的一种立方体数据模型

数据仓库和联机分析处理(OLAP)是商业数据处理领域中的两个最重大的新技术。OLAP应用要求对数据仓库中存储的大量数据进行分析,用标准关系数据库技术来实现非常复杂的查询是相当困难的。所以,在数据仓库中,数据被组织成立方体数据模型。该文提出了一种简单、直观的数据立方体模型以及在这个立方体上支持OLAP操作的代数。为复杂的查询提供了简要的表述方法。     

一种快速生成最小浓缩数据立方的算法

语义OLAP技术是近来学者研究的热点之一,浓缩数据立方就是其中一种.本文设计了一个用于快速生成最小浓缩数据立方的算法SQCube.算法分两个阶段：首先利用BottomUpBST算法生成一个非最小的浓缩数据立方,然后对所得到的非最小浓缩数据立方进行后处理,把其中的所有纯BST和隐BST压缩为一条BST,从而生成一个最小浓缩数据立方.实验表明SQCube算法明显优于以往提出的同类算法MinCube.     

基于数据立方体的网络教学评价模型

网络教学评价是网络教学的一个重要环节。提出了基于数据立方体的网络教学评价模型，以学生、教师为评价对象．构建相应的数据立方体。学生学习行为数据立方体及教师教学行为数据立方体均由六个维度构成，以访问时间作为主要的度量值。并讨论了模型中涉及的关键技术。     

基于数据立方体的网络教学评价模型

网络教学评价是网络教学的一个重要环节。提出了基于数据立方体的网络教学评价模型,以学生、教师为评价对象,构建相应的数据立方体。学生学习行为数据立方体及教师教学行为数据立方体均由六个维度构成,以访问时间作为主要的度量值。并讨论了模型中涉及的关键技术。     

数据方体系统设计中的优化问题

支持实时查询的联机分析处理系统的设计是当前一个很重要的研究问题。其中常用的方法是使用数据方体来实现。对于出现频率较高的查询,可以给出对应的数据方体集,使得每个查询都可以直接得到回答。但是在设计基于方体的系统时,需要考虑以下两个问题:(1)数据方体的维护成本,(2)回答频繁查询的响应时间。在用户给出了维护成本上限和响应时间上限后,需要对数据方体集进行优化,使得系统能够满足用户的要求,并回答尽可能多的查询。文章给出了数据方体系统设计优化问题的定义,这是一个NP完全问题,并提出了贪心删除和贪心合并的近似算法。实验表明了算法的有效性。     

Skyline查询处理数据立方体代数

维空间的Skyline查询处理技术是近年来数据库技术领域的一个研究重点和热点.目前所有的研究工作都是直接在原始数据表上执行关系查询代数操作来获得最终的结果集,然而,随着原始数据表的数据量和维目标个数的增大,这些研究工作将不再适用.基于此,首次研究Skyline集合上的查询代数操作,使得Skyline查询处理的输入数据来自于小规模的Skyline结果集,而非海量的原始数据表.并且,首次给出一个集成多维对象集合和该对象集合上的Skyline结果集的形式化模型,该模型适合目前Skyline查询计算的应用,并在该模型的实例上研究Skyline集合的查询代数操作.同时,给出查询代数体系的代价评估模型.实验表明,给出的数据模型和查询代数体系具有有效性和实用性.     

MS OLAP数据立方自动增量更新的程序实现

针对MS OLAP对海量数据立方体进行完全更新非常耗时,以及在它的服务器管理器中实现数据立方体的手动增最更新操作繁琐,需要由熟悉MDX语言的专业人员完成的问题,文章提出了基于事实表上时间戳或其它标志的自动增量更新方案,并给出了C#编写的程序示例。     

基于数据立方体的多维关联规则的挖掘方法

总结了现有基于数据立方体的多维关联规则挖掘算法,在此基础上将联机分析处理(OLAP)的钻取操作引入关联规则挖掘过程,提出Apriori_cubc算法的改进算法。通过动态调整立方体的维层次,来挖掘出用户感兴趣的关联规则。     

一种高度浓缩和语义保持的数据立方

Quotient Cube和QC-tree试图在浓缩一个数据立方尺寸的同时,保持该数据立方蕴涵的语义,但是,前者没有语义关系的存储,后者存储的语义关系是晦涩模糊的.为此提出了下钻立方结构,首次从语义角度考虑数据立方存储,存储的不是类的内容,而是类之间的直接下钻关系.下钻立方不仅能够极大地减小数据立方的存储尺寸,而且可以清晰地表达原数据立方蕴涵的下钻语义.此外,下钻立方具有较高的查询响应性能,这一点在范围查询中表现得尤其显著.实验和分析表明,下钻立方在存储尺寸和查询响应方面明显优于QC-tree,适于用来组织和存储数据立方.     

基于MapReduce的数据立方体分区优化算法研究

文章利用并行计算框架MapReduce,探索数据立方体的计算问题。数据立方体的计算存在两个关键问题,一个是计算时间的问题,另一个是立方体的体积问题。随着维度的增加,计算时间将呈现指数级的增长,立方体的体积也是如此。尽管MapReduce是一个优秀的并行计算框架,但在处理数据倾斜时,分区算法不够完善,导致一些计算任务时间过长,影响整个作业的完成时间。本文通过数据采样的方式,优化数据分区,实验结果表明,数据立方体的计算的性能明显提升。为解决数据立方体体积过大的问题,在Reduce阶段将最终的结果输出到基于NoSQL的HBase数据库进行存储,HBase方便水平扩展,同时也便于日后对数据立方体的查询。