Thesis IMPLEMENTACIÓN DE UN ALGORITMO APROXIMADO PARA LA ESTRUCTURA PARTITIONED ELIAS-FANO E-OPTIMAL
Date
2022-08
Authors
CARMONA TABJA, GABRIEL ALFREDO
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Las representaciones que permiten comprimir información son útiles en el día de hoy, esto debido a la masividad de la información, por lo que se busca poder comprimir correctamente la información original de tal forma de mantenerla correctamente, pero ocupando menos espacio. Entre las representaciones existen, Partitioned Elias-Fano corresponde a una estructura que permite comprimir la información correctamente, esta estructura tiene dos implementaciones: uniform que consiste en dividir la información en bloques con una cantidad uniforme de 1’s y E-optimal que consiste en dividir la información en bloques de bits con una cantidad variable de 1’s utilizando un algoritmo aproximado. En ambas implementaciones, cada bloque será dividida por separado. Pero, además de comprimir el poder realizar operaciones sobre este conjunto comprimido es importante para no tener que descomprimir la información cada vez que se quiera realizar una consulta. Por esto, se implementaron las operaciones rank y select en la representación Partitioned Elias-Fano y los resultados de las pruebas de estas operaciones indican que si bien esta representación comprime correctamente, los tiempos de estas operaciones son notablemente mayores a otras representaciones.
The representations that allow information to be compressed are useful today, due to the massive amount of available data. For this reason, we seek to compress the original information in such a way as to maintain it while occupying less space. Among the existing representations, Partitioned Elias-Fano corresponds to a structure that allows the information to be compressed correctly. This structure has two implementations: uniform which consists of dividing information into blocks with a uniform amount of 1’s and E−optimal which consist of dividing the information into arrays of bits with a variable quantity of 1’s using an approximate algorithm. In both implementations, each block will be partitioned separately. But, in addition to compressing the ability to perform operations on this set, it is important not to have to decompress the information every time you want to perform a query. For this reason, rank and select were implemented in the Partitioned Elias-Fano representation and the results of the operation tests indicate that although this representation compresses correctly, the execution times of these tests are greater than other representations.
The representations that allow information to be compressed are useful today, due to the massive amount of available data. For this reason, we seek to compress the original information in such a way as to maintain it while occupying less space. Among the existing representations, Partitioned Elias-Fano corresponds to a structure that allows the information to be compressed correctly. This structure has two implementations: uniform which consists of dividing information into blocks with a uniform amount of 1’s and E−optimal which consist of dividing the information into arrays of bits with a variable quantity of 1’s using an approximate algorithm. In both implementations, each block will be partitioned separately. But, in addition to compressing the ability to perform operations on this set, it is important not to have to decompress the information every time you want to perform a query. For this reason, rank and select were implemented in the Partitioned Elias-Fano representation and the results of the operation tests indicate that although this representation compresses correctly, the execution times of these tests are greater than other representations.
Description
Keywords
ALGORITMOS COMPUTACIONALES , COMPRESION DE DATOS (Computadores) , BIG DATA (Volumenes de datos)