Computing data cubes using exact sub-graph matching
Joubert de Castro Lima, Celso Massaki Hirata · 2009
In this paper, we present a novel full cube computation and representation approach, named MCG. In a data cube, each cuboid can be viewed as a set of sub-graphs. In general, redundant sub-graphs are quite common in a data cube, but their elimination is a hard problem as some previous cube approaches demonstrate. The MCG approach differentiates significantly from previous approaches since it efficiently eliminates all common sub-graphs from the entire cube, based on an exact sub-graph matching solution. We propose a matching function to guarantee one-to-one mapping between sub-graphs. The function is computed incrementally, in a top-down fashion, and its computation uses a minimal amount of information to generate unique results, regardless of whether we are using distributive, algebraic or holistic measures. MCG performance analysis demonstrates a similar runtime when compared to Star approach and very low memory consumption (94--98% reduction) when compared to a full cube representation.