Incremental Maintenance of Quotient Cube Based on Galois Lattice

作     者：Cui-PingLi Kum-HoeTung ShanWang 

作者机构：InstituteofComputingTechnologyTheChineseAcademyofSciencesBeijing100080P.R.China SchoolofComputingNationalUniversityofSingaporeSingapore117543 InformationSchoolRenminUniversityofChinaBeijing100872P.R.China 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2004年第19卷第3期

页      面：302-308页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0808[工学-电气工程] 0835[工学-软件工程] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金 国家高技术研究发展计划(863计划) 国家重点基础研究发展计划(973计划) 教育部重点科研项目 

主　　题：Galois lattice quotient cube incremental maintenance 

摘      要：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 quotient cube addressed this fundamental issue through a partitioning method that groups cube cells into equivalent partitions. The effectiveness and efficiency of the quotient cube for cube compression and computation have been proved. However, as changes are made to the data sources, to maintain such a quotient cube is non-trivial since the equivalent classes in it must be split or merged. In this paper, incremental algorithms are designed to update existing quotient cube efficiently based on Galois lattice. Performance study shows that these algorithms are efficient and scalable for large databases.