CubiST++: Evaluating Ad-Hoc CUBE Queries Using Statistics Trees

We report on a new, efficient encoding for the data cube, which results in a drastic speed-up of OLAP queries that aggregate along any combination of dimensions over numerical and categorical attributes. We are focusing on a class of queries called cube queries, which return aggregated values rather than sets of tuples. Our approach, termed CubiST⁺⁺ (Cubing with Statistics Trees Plus Families), represents a drastic departure from existing relational (ROLAP) and multi-dimensional (MOLAP) approaches in that it does not use the view lattice to compute and materialize new views from existing views in some heuristic fashion. Instead, CubiST⁺⁺ encodes all possible aggregate views in the leaves of a new data structure called statistics tree (ST) during a one-time scan of the detailed data. In order to optimize the queries involving constraints on hierarchy levels of the underlying dimensions, we select andmaterialize a family of candidate trees, which represent superviews over the different hierarchical levels of the dimensions. Given a query, our query evaluation algorithm selects the smallest tree in the family, which can provide the answer. Extensive evaluations of our prototype implementation have demonstrated its superior run-time performance and scalability when compared with existing MOLAP and ROLAP systems.     

无须附加空间的数据立方体联机聚集

以往在数据立方体上实现的联机聚集往往需要附加空间来存储联机聚集估算所需要的信息,极大地影响了数据立方体的存储和维护性能.提出了基于QC-Tree的用于范围查询处理的联机聚集PE(progressively estimate)算法以及它与简单聚集算法相结合的混合聚集算法HPE(hybrid progressively estimate);还提出了一种能够同时处理多个范围查询的联机聚集算法MPE(multiple progressively estimate).与以往联机聚集算法不同,这些算法不需要任何附加空间,而是利用QC-Tree自身保存的聚集数据和语义关系来估算聚集结果.由于QC-Tree是一种极为高效的数据立方体存储结构,因此能够以较理想的性能实现数据立方体上的联机聚集.对算法的分析和实验结果表明,所提出的算法具有较好的性能.     

基于数据透视表的多维数据查询技术研究

数据透视表是一种可用于在Web浏览器中动态分析数据的交互式表格。本文介绍了数据透视表的使用以及设计和发布Web数据透视表列表的步骤,并用Access实现了FoodMart2000 Sales多维数据集在浏览器中的多维查询。     

动态数据立方的范围查询

根据data cube层次性的特点和查询习惯提出了新的分块计算方法，并在此基础上提出了改进算法．这种方法节约了存储空间，在LBD粒度及其上的查询效率为O(1)，同时数据的更新时间大约为O()，还节约了大量的存储空间，并且使得数据立方具有了一定的结构独立性，能有效的减少重新构造数据立方(reprocess)的次数，因而在时间上和效率上有较大的优势．     

超大型压缩数据仓库的查询研究

查询速度是联机分析处理中的一个关键性能指标,人们通过事先生成所有可能的聚集来提高查询速度,然而这样的完全物化是以存储空间为代价的.针对数据立方体数据分布特点和结合压缩技术,本文介绍如何最大化节省存储空间来进行完全物化,然后在此基础上对查询进行了研究,以达到最小存储空间以及较好的查询速度的目的.     

基于“C藤”Pair Copula的高维OLAP查询建模方法研究

信息爆炸造成的数据仓库维度的急剧增加,大大影响了OLAP查询模型的精度和效率.首次将数理统计学中的“C藤”Pair Copula引入到OLAP查询建模的研究中,有效地解决了高维OLAP查询建模时的“维数灾难”问题,并设计了针对该模型的参数估计方法以提取数据概要知识.实验分析表明与传统方法相比,基于Pair Copula方法的模型可以在保证OLAP的查询精度的基础上减少数据立方体的存储空间,并且在高维数据环境下具有更高的查询效率.     

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.     

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.     

Hierarchical clustering for OLAP: the CUBE File approach

This paper deals with the problem of physical clustering of multidimensional data that are organized in hierarchies on disk in a hierarchy-preserving manner. This is called hierarchical clustering. A typical case, where hierarchical clustering is necessary for reducing I/Os during query evaluation, is the most detailed data of an OLAP cube. The presence of hierarchies in the multidimensional space results in an enormous search space for this problem. We propose a representation of the data space that results in a chunk-tree representation of the cube. The model is adaptive to the cube’s extensive sparseness and provides efficient access to subsets of data based on hierarchy value combinations. Based on this representation of the search space we formulate the problem as a chunk-to-bucket allocation problem, which is a packing problem as opposed to the linear ordering approach followed in the literature. We propose a metric to evaluate the quality of hierarchical clustering achieved (i.e., evaluate the solutions to the problem) and formulate the problem as an optimization problem. We prove its NP-Hardness and provide an effective solution based on a linear time greedy algorithm. The solution of this problem leads to the construction of the CUBE File data structure. We analyze in depth all steps of the construction and provide solutions for interesting sub-problems arising, such as the formation of bucket-regions, the storage of large data chunks and the caching of the upper nodes (root directory) in main memory. Finally, we provide an extensive experimental evaluation of the CUBE File’s adaptability to the data space sparseness as well as to an increasing number of data points. The main result is that the CUBE File is highly adaptive to even the most sparse data spaces and for realistic cases of data point cardinalities provides hierarchical clustering of high quality and significant space savings.     

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

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

一种并行处理多维连接和聚集操作的有效方法

随着并行计算算法的完善和廉价、功能强大的多处理机系统的成熟,使得采用多处理机系统来并行处理多维数据仓库的连接和聚集操作成为当前有效提高OLAP查询处理性能的首选技术．为此,提出一种降低连接和聚集操作开销的并行算法PJAMDDC(parallel join and aggregation for multi-dimensional data cube)．算法充分考虑了多维数据立方体的存储机制和多处理机分布系统的结构特点,在原有聚集计算多维数据立方体的搜索点阵逻辑结构的基础上,采用多维数据仓库的层次联合代理(hierarchy combined surrogate)和对立方体的搜索点阵进行加权的方法,使得立方体数据在多个处理机间的分配达到最佳的状态,从而在分割多维数据的同时,提高了并行处理多维连接和聚集操作的效率．算法实验评估表明,PJAMDDC算法并行处理多维数据仓库的连接和聚集操作是有效的．     

采用多服务器提高小型OLAP系统综合性能的研究

本文介绍了采用三个服务器并行处理方式的小型OLAP系统，此系统占用最小的存储空间，具有最短的处理时间和最快查速度，除有效地解决了传统系统中请求中子数据聚合的查询速度慢的问题外，同时还满足了系统的可靠性和不间为运地数据更新的要求，文中详细地描述了系统的结构，原理，性能，设计要点和实验结果。     

数据立方体的预计算方法

Cube算子的计算在OLAP应用中起着极为重要的作用。本文分析了在高维Cube算子计算中传统流水线方法的不足之处,提出了通过有选择地实例化Cube中的部分节点以提高OLAP性能的解决方案,并给出了一个获取需要实例化节点的算法。     

Microsoft OLAP Services数据安全性设计

介绍了OLAP系统的基本结构和对Microsoft OLAP Services系统的安全体系进行了全面的分析，最后给出了OLAP数据安全性设计的方案。     

一种OLAP应用系统的设计和实现

通过对数据仓库和OLAP概念及体系结构的分析,描述了一种OLAP应用系统的设计方案,并介绍了它的具体实现方法。基于数据仓库的查询,一般都是及时特定查询,要在严格的响应时间内执行复杂的查询,遍历百万上亿的记录,同时进行可能很复杂的搜索、连接和汇总的操作。查询的数据吞吐量和响应时间是判断数据仓库性能的重点。CUBE的计算是OLAP及时查询的基础,提高查询的速度需要对OLAP进行预先的计算。文中系统比较了一些计算立方体的算法,并运用到具体的系统当中。     

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

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

Parallelizing the Data Cube

This paper presents a general methodology for the efficient parallelization of existing data cube construction algorithms. We describe two different partitioning strategies, one for top-down and one for bottom-up cube algorithms. Both partitioning strategies assign subcubes to individual processors in such a way that the loads assigned to the processors are balanced. Our methods reduce inter processor communication overhead by partitioning the load in advance instead of computing each individual group-by in parallel. Our partitioning strategies create a small number of coarse tasks. This allows for sharing of prefixes and sort orders between different group-by computations. Our methods enable code reuse by permitting the use of existing sequential (external memory) data cube algorithms for the subcube computations on each processor. This supports the transfer of optimized sequential data cube code to a parallel setting.The bottom-up partitioning strategy balances the number of single attribute external memory sorts made by each processor. The top-down strategy partitions a weighted tree in which weights reflect algorithm specific cost measures like estimated group-by sizes. Both partitioning approaches can be implemented on any shared disk type parallel machine composed of p processors connected via an interconnection fabric and with access to a shared parallel disk array.We have implemented our parallel top-down data cube construction method in C++ with the MPI message passing library for communication and the LEDA library for the required graph algorithms. We tested our code on an eight processor cluster, using a variety of different data sets with a range of sizes, dimensions, density, and skew. Comparison tests were performed on a SunFire 6800. The tests show that our partitioning strategies generate a close to optimal load balance between processors. The actual run times observed show an optimal speedup of p.     

一种增量更新FreeCube的方法

数据立方体是联机分析处理的一个重要应用。如何对数据立方体(CUBE)进行更新目前研究相对较少。给出了CUBE的一种新颖的存储结构——FreeCube的定义,该结构大大降低了CUBE存储的空间,分析了它的相关性质,提出了增量更新FreeCube的理论,并给出了具体的算法,以实例说明了该算法的正确性,总结了下一步的工作方向。