缓存敏感的封闭冰山立方体计算

数据立方体计算通常会产生大量的输出结果,冰山立方体和封闭立方体是解决这个问题的比较流行的两种策略,二者可以结合使用.鉴于封闭冰山立方体(closed iceberg cube)的重要性和实用性,如何高效地计算封闭冰山立方体是一个值得研究的问题.提出一种缓存敏感(cache-conscious)的计算封闭冰山立方体的方法,在自底向上对数据进行聚集的同时,寻找覆盖聚集单元的封闭单元,将其输出,使用两种策略进行剪枝,去掉不必要的递归,同时使用Apriori剪枝技术,支持冰山立方体(iceberg cube)的计算.为了减少与内存相关的延迟,快速得到聚集结果,对多个维进行预排序,并将软件预取技术引入到数据扫描中.在模拟数据和真实数据上进行了详细而全面的实验研究,结果表明,封闭冰山立方体的计算方法是快速、有效的.     

基于聚类的非清洁数据库的聚集查询处理算法

现实数据库中的不完整数据、不一致数据、重复数据等非清洁数据为数据库的有效使用带来了影响,从包含非清洁数据的数据库中得到满足清洁度要求的统计分析结果,为数据库研究带来了新的挑战,聚集查询是统计分析的基础.面向非清洁数据,提出了有清洁度保证的聚集查询处理算法,用于处理包含group by子句的聚集查询.考虑到在非清洁数据中,同一个元组可能属于不同的分组,提出的方法是利用可重叠聚类的方法将数据库中的元组加以分组,从而得到考虑数据非清洁性的分组,以及基于这些分组计算得到的聚集结果及其以概率表达的清洁度.提出的方法适用于多种聚集函数以及包含选择条件的聚集查询.通过实验验证了方法的效率.     

基于混合存储结构的数据立方体生成算法

通过把数据立方体中的维分为划分维和非划分维，视图中的数据被分成两部分，分别存储在关系和多维数组中。针对这种混合存储结构，我们设计了一个数据立方体生成算法，它结合了流水线聚集方法和多维数组聚集方法的优点，大大减少了流水线的条数和所需要的存储空间，加快了计算速度。并用一个实际数据集进行了实验，结果表明该算法适用于计算高维的数据立方体。     

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

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

浓缩商覆盖立方体技术研究

提出一种新的浓缩商覆盖立方体的数据立方体压缩技术,在商覆盖立方体中省略了部分只依据基本表即可快速应答查询的基本单元组,从而缩小其体积。给出浓缩商覆盖立方体的生成算法和查询算法。实验结果表明,浓缩商覆盖立方体的元组数量仅为原商覆盖立方体的62%,验证了浓缩商覆盖立方体技术的有效性。     

集合上封闭立方体的计算

随着原始数据记录数的增多,数据立方体在存储空间和计算时间上的消耗都越来越大,封闭立方体是减少数据立方体的存储空间的有效手段。提出一种新的封闭数据立方体的生成算法,针对大量的原始数据集,通过预处理,采用类似BUC算法的计算顺序自上而下递归输出封闭单元,使用实际数据做了相关研究的实验,实验结果表明该算法能有效提高生成速度。     

数据流上的复合滑动窗口聚集算法

基于滑动窗口的聚集查询是数据流研究领域的一个热点问题。在已有的研究工作中,聚集算法都是针对立即执行的连续查询提出的,这些算法均是当数据流新到一个元组立即计算一次聚集结果。而在实际应用中,连续查询有时采取的是周期执行方式。论文针对周期执行的连续查询提出了复合滑动窗口聚集算法,即数据流新到一个元组,将它插入到基本窗口中,当基本窗口被插满时计算一次聚集结果。给出了非增量式和增量式两种算法。理论分析和实验结果表明增量式算法具有较好的性能。     

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

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

在PC集群上的封闭立方体计算

封闭立方体是联机分析处理中一种有效的数据立方体压缩技术,但封闭立方体的并行算法目前很少有相关文献研究.提出了一种简单而实用的解决方案,即基于MapReduce计算框架,在非共享内存的PC集群上对封闭立方体进行分布式的预计算和查询.相关实验表明,本方法能快速处理千万级的数据,具有较好的线性加速比,而且能够更大地压缩数据立方体存储空间.     

用于聚集值近似查询的基于密度的树索引结构

如何快速有效地对数据立方体上的聚集查询给出近似的回答,是数据挖掘和数据仓库研究领域中的核心问题之一。现有大多数聚集查询算法在同一个数据立方体上只能支持某种特定的而非多种类型的聚集查询。本文给出了一种新的框架AdenTS,即基于密度的自适应树结构,它可以回答同一数据立方体上的各类聚集查询,也提出了一些近似和启发式技术,改善了查询结果和精度。实验结果表明,这种方法在支持的查询种类和性能上是更好的。     

Semi-Closed Cube: An Effective Approach to Trading Off Data Cube Size and Query Response Time

The results of data cube will occupy huge amount of disk space when the base table is of a large number of attributes. A new type of data cube, compact data cube like condensed cube and quotient cube, was proposed to solve the problem. It compresses data cube dramatically. However, its query cost is so high that it cannot be used in most applications. This paper introduces the semi-closed cube to reduce the size of data cube and achieve almost the same query response time as the data cube does. Semi-closed cube is a generalization of condensed cube and quotient cube and is constructed from a quotient cube. When the query cost of quotient cube is higher than a given threshold, semi-closed cube selects some views and picks a fellow for each of them. All the tuples of those views are materialized except those closed by their fellows. To find a tuple of those views, users only need to scan the view and its fellow. Thus, their query performance is improved. Experiments were conducted using a real-world data set. The results show that semi-closed cube is an effective approach of data cube.     

实例化视图选择算法PBC

在数据仓库中,如何选择实例化视图是一个重要的问题。针对一类特定的数据立方体,该文提出了一个基于代价策略的实例化视图选择算法。通过对一个实际数据集的分析,发现在数据立方体中有很多父子视图具有相同的体积,其原因是用于产生数据立方体的基本关系的属性之间存在着密切的联系。显然,对这类数据立方体不能像算法PBS那样按照体积的大小来选择要实例化的视图。为此,设计了算法PBC,不但可以快速地给出满足条件的实例化视图集,而且可以准确地找到具有最短平均响应时间的实例化视图集,避免了在用户给出过大的参数时,实例化一些无益于缩短查询响应时间的视图。实验结果表明,算法PBC是有效的。     

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.     

基于Hadoop的封闭直方图立方

封闭数据立方是一种有效的无损压缩技术,它去掉了数据立方中的冗余信息,从而有效降低了数据立方的存储空间、加快了计算速度,而且几乎不影响查询性能.Hadoop的MapReduce并行计算模型为数据立方的计算提供了技术支持,Hadoop的分布式文件系统HDFS为数据立方的存储提供了保障.为了节省存储空间、加快查询速度,在传统数据立方的基础上提出封闭直方图立方,它在封闭数据立方的基础上通过编码技术进一步节省了存储空间,通过建立索引加快了查询速度.Hadoop并行计算平台不论从扩展性还是均衡性都为封闭直方图立方提供了保证.实验证明:封闭直方图立方对数据立方进行了有效压缩,具有较高的查询性能,根据Hadoop的特点通过增加节点个数明显加快了计算速度.     

Efficient Incremental Maintenance for Distributive and Non-Distributive Aggregate Functions

Data cube pre-computation is an important concept for supporting OLAP （Online Analytical Processing） and has been studied extensively. It is often not feasible to compute a complete data cube due to the huge storage requirement. Recently proposed quotient cube addressed this issue through a partitioning method that groups cube cells into equivalence partitions. Such an approach not only is useful for distributive aggregate functions such as SUM but also can be applied to the maintenance of holistic aggregate functions like MEDIAN which will require the storage of a set of tuples for each equivalence class. Unfortunately, as changes are made to the data sources, maintaining the quotient cube is non-trivial since the partitioning of the cube cells must also be updated. In this paper, the authors design incremental algorithms to update a quotient cube efficiently for both SUM and MEDIAN aggregate functions. For the aggregate function SUM, concepts are borrowed from the principle of Galois Lattice to develop CPU-efficient algorithms to update a quotient cube. For the aggregate function MEDIAN, the concept of a pseudo class is introduced to further reduce the size of the quotient cube, Coupled with a novel sliding window technique, an efficient algorithm is developed for maintaining a MEDIAN quotient cube that takes up reasonably small storage space. Performance study shows that the proposed algorithms are efficient and scalable over large databases.     

基于形式概念分析的约简数据立方体研究

数据立方体格和形式概念格比较研究表明,两者都基于序结构,并且采用形式概念分析理论(FCA)的等价特征组与数据立方体覆盖等价类对数据单元有相同的划分结果.将FCA与概念格理论引入数据立方体研究,首次提出聚集概念格(ACL)结构.ACL与一般概念格同构,能完整保存立方体中的所有聚集结果,实现与商立方体相同比例的约简.ACL结构仍比较复杂,在ACL基础上,又提出一种约简聚集概念格结构(RACL),该结构只存储非对象概念,而不是所有概念.RACL与基本表联合仍然是完整立方体结构,但能实现更大的约简.给出了ACL和RACL的高效的查询方法,并使用模拟数据和实际数据作了一些实验.理论和实验都表明RACL结构比现有方法更节省空间,同时查询效率也较高.     

一种数据仓库操作的优化方法

数据立方体在许多多维数据的数据仓库的高速OLAP操作中扮演着重要的角色.但是在许多高维的数据仓库的应用中,例如超过100维,大约106个元组,在这样高维下建立物化数据立方体是不可行的.利用最小方的方法可以在高维数据集上进行有效OLAP操作的方法.但每次进行OLAP操作所涉及的维大多有固定的分布,所以大量的查询都有重复计算.如果能部分物化与大多数OLAP操作相关维的立方体ID,就能在进行OLAP操作时可以大大的提高OLAP操作的效率.