Since the introduction of Data Warehouse (DW) and Online Analytical Processing (OLAP) technologies, efficient computation of data cubes has become one of the most relevant and pervasive problems in the DW area. The data cube operator has exponential complexity; therefore, the materialization of a data cube involves both huge amount of memory and substantial amount of time for its generation. Reducing the size of data cubes, without loss of generality, thus becomes one of the essential aspects for achieving effective OLAP services. Previous approaches reduce substantially the cube size using graph representations. A data cube can be viewed as a set of sub-graphs. In general, the approaches eliminate prefix redundancy and part of suffix redundancy of a data cube. In this work, we propose three major contributions to reduce the data cube size: MDAG, MCG and p-Cube Approaches. The MDAG approach eliminates the wildcard all (*), which represents an entire aggregation, from the cube representation, using the dimensional ID. It also uses the internal nodes to reduce the cube representation height, number of branches and number of common suffixed nodes. Unfortunately, the MDAG approach just reduces the data cube suffix redundancy, so in order to complete eliminate prefix/suffix redundancies we propose the MCG approach. The MCG approach produces a full cube with a reduction ratio of 70-90% when compared to a Star full cube representation. In the same scenarios, the new Star approach, proposed in 2007, reduces only 10-30%, Dwarf 30-50% and MDAG 40-60% of memory consumption when compared to Star approach. Our approaches are, on average, 20-50% faster than Dwarf and Star approaches. In this work, we also propose a parallel cube approach, named p-Cube. The p-Cube approach improves the runtime of Star, MDAG and MCG approaches, while keeping their low memory consumption benefits. The p-Cube approach uses an attribute-based data cube decomposition strategy which combines both task and data parallelism. It uses the dimensions attribute values to partition the data cube into a set of disjoint sub-cubes with similar size. The p-Cube approach provides similar memory consumption among its threads. Its logical design can be implemented in shared-memory, distributed-memory and hybrid architectures with minimal adaptation.

Abordagens para computação de cubos de dados utilizando a estratégia de índices invertidos, tais como Frag-Cubing, são alternativas eficientes em relação às tradicionais abordagens para computação de cubos de dados com alta dimensionalidade, entretanto tais abordagens são limitadas pela memória principal (RAM) disponível. Neste trabalho, é apresentadado duas abordgens iniciais: qCube e H-Frag. qCube é uma extensão da abordagem Frag-Cubing que possibilita consultas de intervalo e H-Frag é uma abordagem que utiliza memória principal e memória externa a partir de definições do usuário. Com base nas abordagens iniciais, propomos duas outras que utilizam o sistema de memória composto por memória principal e memória externa, o qual chamamos de sistema híbrido de memória, para computar e manter atualizado cubos com alta dimensionalidade e elevado número de tuplas: HIC e bCubing. Em HIC, partições de cubos são armazenados em RAM e na memória externa utilizando a mesma representação de Frag-Cubing, contudo valores de atributos frequentes são armazenados em memória principal e valores de atributos pouco frequentes são armazenados em memória externa. HIC utiliza um parâmetro, chamado frequência acumulada crítica, para definir quais os valores de atributo são armazenados em memória principal ou em memória externa. bCubing particiona uma lista de identificadores de tuplas (TIDs) implementando a inversão de tuplas em dois níveis: um nível onde o identificador é o índice de bloco (BID) e o segundo nível onde o identificador é o índice da tupla (TID). As listas de TIDs dos valores de atributos são armazenadas em memória externa. As listas de BIDs são mantidas em memória principal e indexadas pelos valores de atributos. bCubing é capaz de calcular e manter atualizadas medidas holísticas de forma exata em cubos com alta dimensionalidade e elevado número de tuplas. Experimentos utilizando uma relação com 480 dimensões e 107 tuplas mostram que a abordagem bCubing é apenas 30% mais lenta do que Frag-Cubing para computação de cubos e aproximadamente 3 vezes mais rápida para responder consultas multidimensionais complexas a partir de tais relações. Um cubo massivo com 60 dimensões e 109 tuplas foi computado por bCubing usando 84 GB de RAM, enquanto o Frag-Cubing não computou tal cubo em uma máquina com 128 GB de RAM sem realizar operações de swap do sistema operacional. O impacto do cálculo de medidas holísticas em um cubo de dados com alta dimensionalidade também foi avaliado e os resultados demonstram que a abordagem bCubing gasta, em média, 10% mais tempo ao calcular medidas holísticas do que consultas com medidas COUNT. A abordagem bCubing respondeu consultas em um cubo de dados com 1.2 bilhões de tuplas em até 4 minutos, sendo uma destas consultas Q composta por dois operadores de subcubo e um operador EQUAL. A consulta Q calculou três medidas holísticas de forma exata: desvio padrão, mediana e moda.