Un filtro de recuento de Bloom es una estructura de datos generalizada del filtro de Bloom , que se utiliza para probar si un número de recuento de un elemento dado es menor que un umbral dado cuando se proporciona una secuencia de elementos. Como forma generalizada de filtro Bloom , las coincidencias de falsos positivos son posibles, pero los falsos negativos no. En otras palabras, una consulta devuelve "posiblemente mayor o igual que el umbral" o "definitivamente menor que el umbral".
La mayoría de los parámetros se definen igual con el filtro Bloom , como n, k. m es el número de contadores en el filtro Counting Bloom, que es la expansión de m bits en el filtro Bloom. Un filtro de conteo de Bloom vacío es un m contadores, todos configurados en 0. De manera similar al filtro de Bloom, también debe haber k funciones hash diferentes definidas, cada una de las cuales asigna o aplica un hash a algún elemento establecido en una de las m posiciones de la matriz de contadores, lo que genera un distribución aleatoria uniforme. También es similar que k es una constante, mucho más pequeña que m, que es proporcional al número de elementos que se agregarán.
La principal generalización del filtro Bloom es agregar un elemento. Para agregar un elemento, aliméntelo a cada una de las k funciones hash para obtener k posiciones de matriz e incrementar los contadores 1 en todas estas posiciones.
Para consultar un elemento con un umbral θ (probar si el número de recuento de un elemento es menor que θ ), aliméntelo a cada una de las k funciones hash para obtener k posiciones de contador. Si alguno de los contadores en estas posiciones es menor que θ , el número de recuento del elemento es definitivamente menor que θ ; si fuera mayor e igual, entonces todos los contadores correspondientes habrían sido mayores o iguales a θ . Si todos son mayores o iguales a θ , entonces el recuento es realmente mayor o igual a θ , o los contadores por casualidad han sido mayores o iguales a θ. Si todos son mayores o iguales a θ aunque el recuento sea menor que θ , esta circunstancia se define como falso positivo . Esto también debería minimizarse como el filtro Bloom.
Un filtro Bloom de conteo es esencialmente la misma estructura de datos que los bocetos de conteo mínimo , pero se usan de manera diferente.
Varias implementaciones de filtros de floración de conteo permiten la eliminación, al disminuir cada uno de los k contadores para una entrada determinada. Esto introducirá la probabilidad de falsos negativos durante una consulta si la entrada eliminada no se ha insertado previamente en el filtro. Gou et. Alabama. presente el problema con gran detalle y proporcione heurísticas para los parámetros m, kyn que minimizan la probabilidad de falsos negativos. [1]