Un filtro de cuco es una estructura de datos probabilística eficiente en el espacio que se utiliza para probar si un elemento es miembro de un conjunto , como lo hace un filtro Bloom . Las coincidencias de falsos positivos son posibles, pero los falsos negativos no. En otras palabras, una consulta devuelve "posiblemente en el conjunto" o "definitivamente no en el conjunto". Un filtro de cuco también puede eliminar elementos existentes, lo que no es compatible con los filtros Bloom. Además, para aplicaciones que almacenan muchos elementos y tienen como objetivo tasas de falsos positivos moderadamente bajos, los filtros de cuco pueden lograr una sobrecarga de espacio más baja que los filtros Bloom con espacio optimizado. [1]
Los filtros de cuco se describieron por primera vez en 2014 [2].
Descripción del algoritmo
Un filtro de cuco usa un tabla hash asociativa de conjunto de formas basada en hash de cuco para almacenar las huellas dactilares de todos los elementos (cada cubo de la tabla hash puede almacenar hastaentradas). Particularmente, los dos cubos potenciales y en la tabla para un artículo dado requeridos por el hash de cuco se calculan mediante las siguientes dos funciones de hash (denominadas hash de cuco de clave parcial [2] ):
La aplicación de las dos funciones hash anteriores para construir una tabla hash de cuco permite la reubicación del artículo basándose únicamente en las huellas digitales cuando es imposible recuperar el artículo original. Como resultado, al insertar un nuevo artículo que requiere reubicar un artículo existente, la otra ubicación posible en la tabla de este artículo expulsado del cubo es calculado por
Basado en el hash de cuco de clave parcial, la tabla hash puede lograr tanto una alta utilización (gracias al hash de cuco) como compacidad porque solo se almacenan las huellas dactilares. Las operaciones de búsqueda y eliminación de un filtro de cuco son sencillas. Hay un máximo de dos ubicaciones para verificar y . Si se encuentra, la operación de búsqueda o eliminación adecuada se puede realizar enhora. En la literatura se puede encontrar un análisis más teórico de los filtros de cuco. [3] [4]
Comparación con los filtros Bloom
Un filtro de cuco es similar a un filtro de Bloom en el sentido de que ambos son muy rápidos y compactos, y ambos pueden devolver falsos positivos como respuestas a consultas de membresía de conjuntos:
- Uso de filtros Bloom con espacio óptimo bits de espacio por clave insertada, donde es la tasa de falsos positivos. Un filtro de cuco requiere dónde es el factor de carga de la tabla hash, que puede ser basado en la configuración del filtro de cuco. Tenga en cuenta que la información teórica del límite inferior requiere bits para cada elemento.
- En una búsqueda positiva, un filtro Bloom de espacio óptimo requiere una constante la memoria accede a la matriz de bits, mientras que un filtro cucú requiere dos búsquedas constantes como máximo.
- Los filtros de cuco han degradado la velocidad de inserción después de alcanzar un umbral de carga, cuando se recomienda expandir la mesa. Por el contrario, los filtros Bloom pueden seguir insertando nuevos elementos a costa de una tasa de falsos positivos más alta antes de la expansión.
Limitaciones
- Un filtro de cuco solo puede eliminar elementos que se sabe que se insertaron antes.
- La inserción puede fallar y se requiere un refrito como otras tablas de hash de cuco. Tenga en cuenta que la complejidad de inserción amortizada sigue siendo. [5]
Referencias
- ^ Michael D. Mitzenmacher . "Filtros de floración, hash de cuco, filtros de cuco, filtros de cuco adaptables y filtros de floración aprendida" .
- ^ a b Fan, Bin; Andersen, Dave G .; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Filtro de cuco: Prácticamente mejor que Bloom . Proc. 10º ACM International sobre la Conferencia sobre Experimentos y Tecnologías de Redes Emergentes (CoNEXT '14). Sydney, Australia. págs. 75–88. doi : 10.1145 / 2674005.2674994 . ISBN 9781450332798.
- ^ Eppstein, David (22 de junio de 2016). Filtro de cuco: simplificación y análisis . Proc. XV Simposio y Talleres Escandinavos sobre Teoría de Algoritmos (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs). 53 . Reykjavik, Islandia. págs. 8: 1–8: 12. arXiv : 1604.06067 . doi : 10.4230 / LIPIcs.SWAT.2016.8 .
- ^ Fleming, Noah (17 de mayo de 2018). Cuckoo Hashing y Cuckoo Filters (PDF) (Informe técnico). Universidad de Toronto.
- ^ Pagh, Rasmus ; Rodler, Flemming Friche (2001). "Pica de cuco". Proc. Noveno Simposio Europeo Anual de Algoritmos (ESA 2001) . Apuntes de conferencias en informática. 2161 . Århus, Dinamarca. págs. 121-133. doi : 10.1007 / 3-540-44676-1_10 . ISBN 978-3-540-42493-2.