Compactación de cubos en memoria principal con la estructura de datos Arblis

Abstract

Obtener información a partir de bases de datos de gran volumen es posible a través del procesamiento analítico en línea multidimensional (MOLAP, Multidimensional On-Line Analytical Processing). Este procesamiento se lleva a cabo a través de las denominadas Herramientas MOLAP, entre éstas existe el prototipo de software ANTECUMEM (Analizador Temporal de Cubos en Memoria); la cual realiza un manejo multidimensional de los datos a través de estructuras de datos llamadas Arblis dentro de la lattice correspondiente. Se presenta la Estructura Multidimensional AC (Apuntadores a Catálogo) que parte de la estructura de cubos de datos Arblis comprimida, llevándose a cabo una compactación de tamaño en disco duro y en memoria principal de tal forma que se logre una navegación a través de este cubo de datos además del aumento en la cantidad de datos que pueden ser accedidos y por ello acumulados en el mismo espacio. El desarrollo del diseño de compactación de los datos en Arblis se obtiene a través del estudio de diversos métodos: eliminación de los ítems de datos redundantes, conversión a notación compacta, supresión de caracteres repetidos sucesivamente, evitar espacios vacíos, sustitución de datos repetidos, sustitución de texto idiomáticos, algoritmo de Huffman, algoritmo de Shannon-Fano y algoritmo LZW (Lempel Ziv Welch). La compactación seleccionada se obtiene tomando en cuenta los métodos mencionados así como las características de navegabilidad y orden presentes en Arblis obteniendo cuatro propuestas viables: arreglos con elementos vacíos, arreglos sin elementos vacíos, mapas de bits y apuntadores a catálogo (AC); siendo seleccionada la última ya que se adaptaba más a las necesidades. Una vez que se tiene materializada la estructura, ésta es cargada en memoria principal haciendo uso de la vista más grande de la lattice, de tal forma que son cargadas las n dimensiones del cubo de datos. Una vez que se tiene en memoria principal pueden ser contestadas siete tipo de consultas originarias de ANTECUMEM: pregunta puntual, pregunta de rangos, pregunta de eficiencia global, pregunta de eficiencia grupal, preguntas sobre la conservación y pérdida, pregunta de temporalidad y pregunta de tendencia. A dichos algoritmos se les aplicó una modificación mínima al realizarse la compactación a pesar de que la búsqueda se realiza en la estructura compresa. ANTECUMEM permite tener una estructura de diez dimensiones y la manipulación simultánea de hasta cuatro dimensiones. Por lo que se realizan las modificaciones pertinentes para manejar n dimensiones en la creación de AC y la manipulación de ésta para la solución de las siete preguntas antes mencionadas. De tal forma que el manejo del cubo de datos es de n dimensiones limitado únicamente por la cantidad de memoria. // Representación de almacenamiento de datos, ANTECUMEM, Estructura AC. // To get information from a huge data base is possible through the Mutidimensional On-Line Analytical Processing (MOLAP). This processing is done by MOLAP Tools, between them, exist a prototype of software that performs such action, it is called ANTECUMEM (Temporal Analyzer Memory Cubes); that makes a multidimensional data management through data structures called Arblis for each node in the lattice. The Multidimensional Data Structure AC (Catalog Pointers) is presented, based on the concept of the data cube structure Arblis but compress, it is done with a compression in hard disc and main memory, so that navigation thorough that data cube could be possible, in addition of the increase in the amount of data that can be accumulated and therefore accessed in the same space. The design development of the data compression in Arblis is obtained through the study of different methods: elimination of redundant data items, converting to compact notation, removal repeated characters, to avoid empty spaces, replacing redundant data, replacing idiomatic text, Huffman algorithm, Shannon-Fano algorithm and LZW algorithm (Lempel Ziv Welch). The selected compression is obtained by taking into account the above methods and the characteristics of navigability and order that Arblis has, getting four viable proposals: arrays with empty elements, arrangements without empty elements, bitmaps and catalog pointers (AC), being the last one was selected because it filled the requirements. Once the structure AC is materialized, it is loaded into main memory using the largest view of the lattice, so we would have a n-dimensional data cube. Once it is in main memory, seven types of queries originated from ANTECUMEM can be answered: punctual question, ranking question, global efficiency question, group efficiency question, preservation and loss question, and temporary trend question. For those algorithms, it was applied the minimum modifications when the compression was done, even though that the search is done in the compress data structure (AC). ANTECUMEM allows a ten-dimensional structure and the simultaneous use of four dimensions. So therefore the appropriate changes are done in order to handle a n-dimensional structure in the moment of the creation of AC and manipulation of AC for the solution of the seven questions above. So that the use of the data cube AC of n dimensions is limited only by the amount of memory.