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

Cache-Conscious Computation of Closed Iceberg Cubes

作　　者：栾华 杜小勇[1,2] 王珊[1,2] 

机构地区：[1]数据工程与知识工程教育部重点实验室(中国人民大学),北京100872 [2]中国人民大学信息学院,北京100872

出　　处：《软件学报》2010年第4期620-631,共12页Journal of Software

基　　金：国家自然科学基金Nos.60496325;60873017;惠普中国实验室资助项目~~

摘　　要：数据立方体计算通常会产生大量的输出结果,冰山立方体和封闭立方体是解决这个问题的比较流行的两种策略,二者可以结合使用.鉴于封闭冰山立方体(closed iceberg cube)的重要性和实用性,如何高效地计算封闭冰山立方体是一个值得研究的问题.提出一种缓存敏感(cache-conscious)的计算封闭冰山立方体的方法,在自底向上对数据进行聚集的同时,寻找覆盖聚集单元的封闭单元,将其输出,使用两种策略进行剪枝,去掉不必要的递归,同时使用Apriori剪枝技术,支持冰山立方体(iceberg cube)的计算.为了减少与内存相关的延迟,快速得到聚集结果,对多个维进行预排序,并将软件预取技术引入到数据扫描中.在模拟数据和真实数据上进行了详细而全面的实验研究,结果表明,封闭冰山立方体的计算方法是快速、有效的.The computation of data cubes this problem： Iceberg cube and closed cube, usually produces huge outputs. There which can be combined together. Due are two popular methods to solve to the importance and usability of closed iceberg cube, how to efficiently compute it becomes a key research issue. A cache-conscious computation method is proposed in this paper. The data are aggregated in a bottom-up manner. In the meantime, the closed cells covering the aggregate cells are discovered and output. Two pruning strategies are used to save unnecessary recursive calls. The Apriori pruning is utilized to support iceberg cube computation. To reduce the number of memory-related stalls and produce the aggregate results efficiently, multiple dimensions are pre-sorted and the software prefetching technology is introduced into data scans. A comprehensive and detailed performance study is conducted on both synthetic data and real data sets. The results show that the proposed closed iceberg cube computation method is efficient and effective.

关 键 词：联机分析处理 封闭冰山立方体 缓存敏感 内存相关延迟 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]