Estrutura híbrida para melhoria de desempenho dos Roaring Bitmaps para consultas rank

Abstract

Desde o desenvolvimento das primeiras estruturas de dados compactadas, uma variedade de estudos foi realizada, com o objetivo de alcançar um desempenho computacional próximo ao das estruturas não compactadas, relativamente a operações de consulta [1, 5, 9, 12, 16], . Dentre as abordagens propostas até o momento, a viabilidade matemática dessas estruturas nem sempre corresponde à realidade prática [17]. Nesse contexto, desenvolver algoritmos e estruturas de dados eficientes tem sido uma constante no mundo das operações de consulta. Este trabalho avalia a viabilidade dos Roaring Bitmaps para a operação de rank (i.e. retornar a soma de bits 1, do início do vetor até uma dada i-ésima posição) e melhorar seu desempenho, além de compará-lo, antes e depois de algumas modificações, com o desempenho de estruturas especializadas em ranks, examinadas em [16] e [17]. Mostramos como é possível substituir um algoritmo que realiza contagem de bits, utilizando 2^10 operações de popcount em um vetor de bits de tamanho fixo, por uma operação em tempo constante que realiza consulta a uma estrutura auxiliar, capaz de, em um dos cenários explorados, reduzir o tempo de execução em 95,65%. Em seguida, mostramos como tornar constante o tempo total de execução das consultas rank com os Roaring Bitmaps com praticamente o mesmo uso de memória. Nós concluímos que utilizar uma estrutura auxiliar que utiliza 6,25% a mais de memória com os Roaring Bitmaps é superior a utilizar a versão original, por manter a complexidade de espaço e reduzir a complexidade de tempo. Concluímos também que, na versão final dos Roaring Bitmaps modificados, é necessário criar uma restrição sobre a adição de valores representativos dos conjuntos de inteiros, para que seja possível tornar as operações nos Roaring Bitmaps constantes no tempo, porque a otimização final foi possível considerando o seguinte caso: as consultas rank são realizadas após finalizada a adição de inteiros aos Bitmaps.