Filtro de cuco

Un filtro cuco es una estructura de datos probabilística que optimiza el espacio y se utiliza para comprobar si un elemento pertenece a un conjunto , al igual que un filtro Bloom . Son posibles los falsos positivos , pero no los falsos negativos ; en otras palabras, una consulta devuelve "posiblemente en el conjunto" o "definitivamente no en el conjunto". Un filtro cuco también puede eliminar elementos existentes, función que no admiten los filtros Bloom. Además, para aplicaciones que almacenan muchos elementos y buscan tasas de falsos positivos moderadamente bajas, los filtros cuco pueden lograr una menor sobrecarga de espacio que los filtros Bloom optimizados para el espacio. ^{[ 1 ]}

Los filtros Cuckoo se describieron por primera vez en 2014. ^{[ 2 ]}

Un filtro cuco utiliza una tabla hash basada en el hash cuco para almacenar las huellas digitales de los elementos. ^{[ 2 ]} La estructura de datos se divide en cubos de cierto tamaño.${\displaystyle b}$Para insertar la huella digital de un artículo${\displaystyle x}$, primero se calculan dos posibles cubetas${\displaystyle h_{1}(x)}$y${\displaystyle h_{2}(x)}$dónde${\displaystyle x}$podrían ir. Estos cubos se calculan utilizando la fórmula

${\displaystyle h_{1}(x)={\text{hash}}(x)}$

${\displaystyle h_{2}(x)=h_{1}(x)\oplus {\text{hash}}({\text{huella digital}}(x))}$

Nótese que, debido a la simetría de la operación XOR , se puede calcular${\displaystyle h_{2}(x)}$de${\displaystyle h_{1}(x)}$, y${\displaystyle h_{1}(x)}$de${\displaystyle h_{2}(x)}$. Como se definió anteriormente,${\displaystyle h_{2}(x)=h_{1}(x)\oplus {\text{hash}}({\text{huella digital}}(x))}$; de ello se deduce que${\displaystyle h_{1}(x)=h_{2}(x)\oplus {\text{hash}}({\text{huella digital}}(x))}$Estas propiedades son las que permiten almacenar las huellas digitales con el algoritmo de hash Cuckoo.

La huella dactilar de${\displaystyle x}$se coloca en uno de los cubos${\displaystyle h_{1}(x)}$y${\displaystyle h_{2}(x)}$Si los depósitos están llenos, una de las huellas digitales del depósito se elimina mediante el algoritmo de hash Cuckoo y se coloca en otro depósito donde pueda ir. Si ese depósito también está lleno, puede desencadenarse otra eliminación, y así sucesivamente.

La tabla hash puede lograr tanto una alta utilización (gracias al hash cuckoo ) como compacidad, ya que solo se almacenan huellas digitales. Las operaciones de búsqueda y eliminación de un filtro cuckoo son sencillas. ^{[ 2 ]}

Hay un máximo de dos cubos para revisar${\displaystyle h_{1}(x)}$y${\displaystyle h_{2}(x)}$. Si se encuentra, se puede realizar la operación de búsqueda o eliminación correspondiente en${\displaystyle O(b)}$tiempo. A menudo, en la práctica,${\displaystyle b}$es una constante.

Para que la tabla hash ofrezca garantías teóricas, el tamaño de la huella digital${\displaystyle f}$debe ser al menos${\displaystyle \Omega ((\log n)/b)}$bits. ^{[ 2 ] [ 3 ] [ 4 ]} Sujeto a esta restricción, los filtros cuckoo garantizan una tasa de falsos positivos de como máximo${\displaystyle \epsilon \leq b/2^{f-1}}$. ^{[ 2 ]}

Un filtro cuco es similar a un filtro Bloom en el sentido de que ambos son rápidos y compactos, y ambos pueden devolver falsos positivos como respuestas a consultas de pertenencia a conjuntos:

• Los filtros Bloom de uso óptimo del espacio${\displaystyle 1.44\log _{2}(1/\epsilon )}$bits de espacio por tecla insertada, donde${\displaystyle \epsilon }$es la tasa de falsos positivos. Un filtro de cuco requiere${\displaystyle (\log _{2}(1/\epsilon )+1+\log _{2}b)/\alpha }$espacio por clave ^{[ 2 ]} donde${\displaystyle \alpha }$es el factor de carga de la tabla hash, que puede ser${\displaystyle 95.5\%}$basado en la configuración del filtro cuco. Tenga en cuenta que el límite inferior teórico de la información requiere${\displaystyle \log _{2}(1/\epsilon )}$bits para cada elemento. Tanto los filtros Bloom como los filtros Cuckoo con baja carga se pueden comprimir cuando no se utilizan.
• En una búsqueda positiva, un filtro Bloom óptimo en cuanto al espacio requiere una constante${\displaystyle \log _{2}(1/\epsilon )}$accesos a la memoria en la matriz de bits , mientras que un filtro cuco requiere como máximo${\displaystyle 2b}$accesos a la memoria, que pueden ser una constante en la práctica.
• Los filtros Cuckoo presentan una velocidad de inserción reducida tras alcanzar un umbral de carga, momento en el que se recomienda expandir la tabla. En cambio, los filtros Bloom pueden seguir insertando nuevos elementos a costa de una mayor tasa de falsos positivos antes de la expansión.
• Los filtros Bloom ofrecen operaciones rápidas de unión e intersección aproximada mediante operaciones bit a bit económicas, que también se pueden aplicar a filtros Bloom comprimidos si se utiliza compresión de flujo.

• Un filtro Cuckoo solo puede eliminar elementos que se sabe que se insertaron previamente.
• La inserción puede fallar y se requiere un rehash como en otras tablas hash de Cuckoo. Tenga en cuenta que la complejidad de inserción amortizada sigue siendo${\displaystyle O(1)}$. ^{[ 5 ]}
• Los filtros Cuckoo requieren un tamaño de huella dactilar.${\displaystyle f}$de al menos${\displaystyle \Omega ((\log n)/b)}$bits. Esto significa que el espacio por clave debe ser al menos${\displaystyle (\log n)/b}$bits, incluso si${\displaystyle \epsilon }$es grande. En la práctica,${\displaystyle b}$se elige que sea lo suficientemente grande como para que esto no sea un problema importante. ^{[ 2 ]}

• Filtros probabilísticos mediante ejemplos: un tutorial que compara los filtros Cuckoo y Bloom.