OPTIMIZACIÓN DE OPERACIONES SOBRE VECTORES DE BITS CODIFICADOS EN WORD ALIGNED HYBRID

Abstract

Las estructuras de datos compactas son representaciones de estructuras de datos más complejas, y que ofrecen funcionalidad y acceso a datos de manera eficiente en términos de espacio. Una de las estructuras de datos compactas más típicas son los vectores de bits, conocidos también como bitmaps o arreglo de bits. Su uso en diversas áreas es bastante amplio, sirviendo de base para la definición de estructuras de datos sucintas existente. Sobre estos vectores es importante soportar distintas consultas, las cuales resultan esenciales en varios tipos de estructuras compactas, como árboles, estructuras comprimidas para búsqueda en texto, grafos, funciones y permutaciones, entre otros. Existen numerosas técnicas que realizan estas consultas sobre vectores de bits, las cuales utilizan distintas maneras para codificar los datos y responder a las consultas. Todas estas técnicas difieren tanto en los tiempos en que las consultas son soportadas, como en el espacio que deben utilizar para responderlas, por lo que es importante lograr un balance entre el tiempo de consulta y el espacio que se utiliza en cada consulta. Una de las codificaciones utilizadas hoy en día sobre bitmaps es la codificación Word Aligned Hybrid (WAH), la cual es ampliamente utilizada en bases de datos. En el presente trabajo, se propone una implementación de las operaciones sobre vectores de bits codificados en WAH. Posteriormente se analizara su rendimiento en términos de tiempo y espacio y finalmente se comparara con los métodos existentes en el estado del arte.

Compact data structures are representations of complex ones, that offer eficient data access and functionality, in terms of space. One of the most common data structures are bit vectors, known as bitmaps or bit arrays. They are widely used in different areas, being the base of other compact data structures. Upon these vectors can be made a series of queries, which are essential in many types of compact data structures, such as trees, compressed structures for text searching, graphs, functions and permutations, between others. There are a lot of tecniques that answer queries upon bit vectors, which use different ways to encode data and answer queries. All of these tecniques have different query timings and different space use, the refore is important to achieve a balance betwen query timing and space. One of the coding algorithms is the one called Word Aligned Hybrid (WAH), which is widely used in data bases. In this work, we propose a implementation of several operations upon WAH encoded bit vectors. After that we will analize it’s performance in terms of timing and space and we will compare with the methods currently in the State of Art.