Quotient Cube: A Semantic Approach to Data Cube Compression

Laks V.S. Lakshmanan
University of British Columbia

In this talk, I will describe a lossless compression technique inspired by concepts from lattice theory. Specifically, I will discuss the Quotient Cube, which is the factor lattice obtained when the cube lattice is “divided” by a certain equivalence relation. The idea is to represent cube cells by choosing a representative from the equivalence class they are in. In a precise sense, we can show that the quotient cube is an optimal lossless compression of a data cube. I will also describe the QC-Tree, an efficient data structure for storing a quotient cube as well as our algorithm for computing a quotient cube from a base table. QC-Trees can be used for efficient answering of queries and for efficient incremental maintenance against updates to the base table. Detailed experimental evaluations show that quotient cubes (implemented via QC-Trees) enjoy a substantial reduction in the cube size while at the same time enabling fast and scalable construction, query answering, and incremental maintenance performance. This is joint work with Jiawei Han, Jian Pei, and Yan Zhao.