Resumen

Los filtros Bloom son estructuras de datos aleatorias y eficientes en términos de espacio para consultas rápidas de pertenencia, que permiten falsos positivos. Los filtros de Bloom de recuento (CBF) realizan las mismas operaciones en conjuntos dinámicos que pueden actualizarse mediante inserciones y supresiones. Los CBF se han utilizado ampliamente en MapReduce para acelerar el procesamiento de datos a gran escala en grandes clústeres reduciendo el volumen de los conjuntos de datos. La probabilidad de falsos positivos de CBF debe ser lo más baja posible para filtrar los conjuntos de datos más redundantes. En este artículo, proponemos un enfoque de optimización multinivel para construir un filtro Bloom de recuento preciso (ACBF) con el fin de reducir la probabilidad de falsos positivos. El ACBF se construye particionando el vector contador en múltiples niveles. Proponemos un ACBF optimizado maximizando el tamaño del primer nivel, para minimizar la probabilidad de falsos positivos manteniendo la misma funcionalidad que el CBF. Los resultados de la simulación muestran que el ACBF optimizado reduce la probabilidad de falsos positivos hasta en un 98,4 con el mismo consumo de memoria que CBF. También implementamos ACBFs en MapReduce para acelerar la unión del lado de reducción. Los experimentos con conjuntos de datos realistas muestran que ACBF reduce la probabilidad de falsos positivos en un 72,3 s así como las salidas de mapas en un 33,9 y mejora los tiempos de ejecución de la unión en un 20 % en comparación con CBF.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:probabilidad de falsos positivos, acbf, cbf, filtro bloom de recuento preciso, estructuras de datos aleatorias eficientes, consultas rápidas de pertenencia, tamaño de primer nivel, tiempos de ejecución de uniones, enfoque de optimización multinivel, mismo consumo de memoria.
• Keywords:false positive probability, acbf, cbf, accurate counting bloom filter, efficient randomized data structures, fast membership queries, first level size, join execution times, multilevel optimization approach, same memory consumption