Análise do erro de estimação em Filtros de Bloom Lineares

Abstract

O registo preciso de grandes volumes de dados requer uma, proporcionalmente, grande quantidade de memória. Uma forma de reduzir esta necessidade passa por fazer um registo probabilístico com recurso à técnica de Filtros de Bloom. Esta técnica permite detetar, com uma determinada probabilidade de erro por falsos positivos, a pertença de um elemento a um conjunto. Pretende-se, nos Filtros de Bloom Lineares, generalizar esta técnica para associar um valor numérico a cada elemento e permitir a consulta desse valor. Torna-se assim possível a sua aplicação a situações onde se pretende qualificar numericamente os valores registados, como por exemplo na atribuição de um grau de confiança numérico a uma observação registada. Neste projeto é feito um estudo analítico do erro esperado na consulta, em função da distribuição dos valores inseridos, nomeadamente para as distribuições: Uniforme, Exponencial ou Normal. Este estudo envolve a aplicação da teoria de valores extremos, usando a função generalizada de valores extremos e a função densidade de mínimos de máximos deduzida. Com a ajuda do software estatístico R, efetuaram-se estudos de simulação do funcionamento dos Filtros de Bloom Lineares. Comparando o resultado dessas simulações face ao estudo analítico baseado na teoria de valores extremos, concluiu-se com ótimos resultados que o erro esperado é reduzido, para enchimentos convencionais do filtro, e que há um bom ajuste entre as funções teóricas e os resultados experimentais.

The precise recording of large volumes of data requires a proportionally big amount of memory. Memory usage can be reduced by using Bloom Filters as a probabilistic representation of the data to be stored. This technique allows detecting, with a given probability for false positives, if an element belongs, or not, to a set. In an extension of the technique, Linear Bloom Filters, set membership is generalized in order to associate a numerical value to each element and allow the query to retrieve that value. This permits the application to settings where one intends to qualify numerically the registered values, for example in the attribution of a numeric quality degree to a registered observation. In this project the analytic study of the query’s expected error is done, depending on the distribution of the inserted values, for the Uniform, Exponential and Normal distributions. This study applies the extreme values theory, using the generalized function of extreme values and the derived density function of maxima minima. With the help of R statistical software, several simulation studies of the operation of Bloom Linear Filters were made. By comparing the result of the simulations with the analytic study based on the extreme values theory, it was possible to conclude with good confidence that the expected error is small, for conventional fillings of the filter, and that there exists a good adjustment between the theoretical functions and the experimental results.