一种基于Dwarf的快速有效增量更新算法  

A Dwarf-based Fast and Efficient Incremental Update Algorithm

作　　者：印莹[1,2] 赵宇海[1,2] 张斌[1,2] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110004 [2]鞍山师范学院数学系,鞍山114001

出　　处：《计算机科学》2005年第11期88-90,129,共4页Computer Science

基　　金：国家自然科学基金(No.60273079;No.60473074;2004BA721A05)

摘　　要：数据立方计算是代价非常大的操作,并且被广泛研究。受空间的限制,存储一个完全实例化的数据立方是不可行的。最近提出的一种语义压缩数据立方—Dwarf,通过消除前缀冗余和后缀冗余把一个完全实例化的数据立方压缩存储到一个很小的空间。然而,当数据源发生变化时,它的更新过程是很复杂的。本文通过研究Dwarf在更新过程中汇总结点的变化特性,提出了一种基于Dwarf的新的增量更新算法,既能完全实例化数据立方又不需要重新计算,大大提高了数据立方的更新效率。实验进一步证明了该算法的效率和有效性,尤其适合数据仓库中的高维数据集。Data cube computation is a well-known expensive operation and has been studied extensively. It is often not feasible to compute a complete data cube due to the huge storage requirement. Recently proposed Dwarf cube com- pressed the complete data cube into a dramatically condensed data structure through the elimination of prefix and suffix redundancy. However, as changes are made to the data sources, to update such a Dwarf cube in time is non-trivial, In this paper, we propose a new Dwarf-based optimized update algorithm on the basis of studying the characters of sum- marized node, which can materialize all of data cubes fully and requires no recalculation. The algorithm improves the updating performance of the data cube obviously. Furthermore, the effectiveness and efficiency of this algorithm have been shown by experimental results, especially for the high dimension data warehouses.

关 键 词：数据仓库 前缀冗余 DWARF 增量更新 增量更新算法 数据立方 压缩存储 更新过程 实例化 发生变化 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] TP301.6[自动化与计算机技术—计算机科学与技术]