一种构造QC-Tree的单阶段算法  

One-phase Algorithm for QC-tree Construction

作　　者：向隆刚[1] 龚健雅[1] 

机构地区：[1]武汉大学测绘遥感信息工程国家重点实验室,湖北武汉430079

出　　处：《小型微型计算机系统》2007年第10期1865-1868,共4页Journal of Chinese Computer Systems

基　　金：国家"九七三"重点基础研究发展计划项目(2006CB701300)资助.

摘　　要：QC-tree是一种组织数据立方的有效数据结构,不仅可以降低数据立方的存储开销,而且能够保持数据立方的语义关系.QC-tree的原始构造算法分为两个阶段,由于涉及到临时类的生成和处理,构造性能很低.为此,本文研究了QC-tree结构,导出了两个关于事实表划分和前缀路径的重要定理,在此基础上提出了构造QC-tree的单阶段算法,即OPA算法.实验和分析表明,OPA算法的构造效率远远优于原始构造算法.此外,OPA算法大大降低了对于工作内存的需求.QC-tree is an effective data structure for data cube, which can not only reduce the storage size of a data cube, but also keep its semantics. The original construction algorithm insists of two parts, performing very poor when constructing QC- trees, due to the generating and processing of temporary classes. To solve the problem, the QC-tree structure is explored, leading two important lemmas about fact table partition and prefix-path. Based on the two lemmas, this paper proposes a onephase algorithm, called OPA, for the construction of QC-tree. OPA algorithm outperforms the original algorithm significantly and besides, it releases the work memory requirement greatly.

关 键 词：数据立方 QC-tree 划分 前缀路径 

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