Los filtros de consulta de pertenencia aproximada (en adelante, filtros AMQ) comprenden un grupo de estructuras de datos probabilísticas que ahorran espacio y que admiten consultas de pertenencia aproximada. Una consulta de pertenencia aproximada responde si un elemento está en un conjunto o no con una tasa de falsos positivos de .
Los filtros Bloom son los filtros AMQ más conocidos, pero existen otros filtros AMQ que admiten operaciones adicionales o tienen diferentes requisitos de espacio.
Los filtros AMQ tienen numerosas aplicaciones, principalmente en sistemas distribuidos y bases de datos, donde suelen utilizarse para evitar solicitudes de red o operaciones de E/S que resultan de solicitar elementos que no existen.
El problema de consulta de pertenencia aproximada consiste en almacenar información sobre un conjunto de elementos S de una manera que abarque el espacio. El objetivo es responder a consultas sobre si un elemento x está o no en el conjunto S , al tiempo que se restringen los falsos positivos a una probabilidad máxima . Todos los filtros AMQ admiten esta operación de búsqueda. Los filtros AMQ dinámicos permiten inserciones en cualquier momento, mientras que los filtros AMQ estáticos deben reconstruirse después de insertar elementos adicionales. Algunos filtros AMQ admiten operaciones adicionales, como eliminar elementos o fusionar dos filtros.
Una búsqueda de filtro AMQ determinará si un elemento definitivamente no está en el conjunto o probablemente sí lo está.
En otras palabras, si el filtro representa un conjunto S y nos interesa un valor s , entonces la función de búsqueda aplicada a s se comporta de la siguiente manera:
Un falso positivo es una búsqueda de un elemento que no forma parte del conjunto, pero en la que el resultado de la búsqueda es verdadero. La probabilidad de que esto ocurra es la tasa de falsos positivos . Los falsos negativos (la búsqueda devuelve falso aunque el elemento forma parte del conjunto) no están permitidos en los filtros AMQ.
Después de insertar un elemento, la búsqueda de este elemento debe devolver verdadero. Los filtros AMQ dinámicos permiten insertar elementos de a uno por vez sin tener que reconstruir la estructura de datos. Otros filtros AMQ deben reconstruirse después de cada inserción. Se denominan filtros AMQ estáticos.
Existe una compensación entre el tamaño de almacenamiento y la tasa de falsos positivos . Aumentar el espacio de almacenamiento reduce la tasa de falsos positivos. El límite inferior teórico es de bits para cada elemento. [1] Los filtros AMQ dinámicos no pueden alcanzar este límite inferior. Necesitan al menos bits para las inserciones. [2] Los diferentes filtros AMQ tienen diferentes rangos de tasas de falsos positivos y requisitos de espacio. La elección del mejor filtro AMQ depende de la aplicación.
Existen diferentes formas de resolver el problema de consulta de pertenencia aproximada. La estructura de datos más conocida son los filtros Bloom , pero existen otras estructuras de datos que funcionan mejor para ciertas tasas de falsos positivos y requisitos de espacio, admiten operaciones adicionales o tienen otros tiempos de inserción y búsqueda. A continuación, describimos algunos filtros AMQ conocidos.
Un filtro Bloom es una matriz de bits con funciones hash. Cada función hash asigna un elemento a una de las posiciones de la matriz. Al principio, todos los bits de la matriz se establecen en cero. Para insertar un elemento, se calculan todas las funciones hash y todos los bits correspondientes de la matriz se establecen en uno. Para buscar un elemento, se calculan todas las funciones hash. Si se establecen todos los bits correspondientes, se devuelve . Para reducir la tasa de falsos positivos, se puede aumentar la cantidad de funciones hash y .true
La idea de los filtros de cociente es hacer un hash de un elemento y dividir su huella digital en los bits menos significativos, llamados resto , y los bits más significativos, llamados cociente . El cociente determina en qué parte de la tabla hash se almacena el resto. Se utilizan tres bits adicionales por cada ranura de la tabla hash para resolver colisiones suaves (mismo cociente pero diferentes restos).
El espacio utilizado por los filtros de cociente es comparable al de los filtros Bloom, pero los filtros de cociente se pueden fusionar sin afectar su tasa de falsos positivos.
Los filtros Cuckoo se basan en el hash Cuckoo , pero solo se almacenan las huellas digitales de los elementos en la tabla hash. Cada elemento tiene dos ubicaciones posibles. La segunda ubicación se calcula en función de la primera ubicación y la huella digital del elemento. Esto es necesario para permitir mover elementos ya insertados si ambas ranuras posibles para un elemento están llenas.
Después de alcanzar un umbral de carga, la velocidad de inserción del filtro cuco disminuye. Es posible que una inserción falle y que la tabla deba volver a procesarse. Mientras que los filtros Bloom tienen un tiempo de inserción siempre constante, a medida que aumenta el factor de carga, también aumenta la tasa de falsos positivos.
Un filtro cuco permite eliminar elementos en el caso de que sepamos con certeza que el elemento ya se había insertado previamente. Esto supone una ventaja con respecto a los filtros Bloom y los filtros de cociente, que no admiten esta operación.
Los filtros XOR [3] son filtros AMQ estáticos que se basan en un filtro Bloomier y utilizan la idea de tablas hash perfectas . De manera similar a los filtros cuckoo, guardan huellas digitales de los elementos en una tabla hash. La idea es que una consulta para un elemento es verdadera si el XOR de tres funciones hash dadas es la huella digital de . Al construir la tabla hash, a cada elemento se le asigna una de sus tres ranuras de manera que ningún otro elemento se asigna a esta ranura. Después de que todos los elementos están asignados, establecemos para cada elemento el valor de su ranura al XOR de las otras dos ranuras (no asignadas) del elemento y la huella digital del elemento. Este algoritmo de construcción puede fallar de manera tal que no sea posible realizar inserciones dinámicas sin reconstruir la tabla hash. Esta tabla hash se puede construir utilizando solo bits por elemento.
La desventaja de este filtro es que la estructura de datos debe reconstruirse si se agregan elementos adicionales. Se utilizan en aplicaciones en las que no es necesario agregar elementos posteriormente y el espacio es importante.
Las aplicaciones típicas de los filtros AMQ son los sistemas distribuidos y los sistemas de bases de datos. El filtro AMQ funciona como un proxy del conjunto de claves de una base de datos o de una memoria remota. Antes de que se realice una consulta presuntamente lenta a la base de datos o a la memoria remota, se utiliza el filtro AMQ para dar una respuesta aproximada sobre si la clave está en la base de datos o en la memoria remota. La consulta lenta solo se realiza cuando el filtro AMQ devuelve verdadero. Solo en el caso de un falso positivo (que esperemos que sea poco frecuente) se realiza una E/S innecesaria o un acceso remoto. Las aplicaciones son numerosas e incluyen el enrutamiento de paquetes y recursos, las redes P2P y el almacenamiento en caché distribuido. [4]
Los filtros AMQ se utilizan a menudo como una estructura de datos en memoria para evitar costosos accesos al disco. Una aplicación son los árboles de fusión estructurados en forma de registro o árboles LSM. Tienen un componente rápido en memoria y uno o varios componentes en un disco que son árboles en sí mismos. Los elementos se insertan en el componente en memoria hasta que alcanza su tamaño máximo, luego el componente en memoria se fusiona con los componentes del disco. Para acelerar la búsqueda, muchos árboles LSM implementan filtros AMQ como filtros Bloom o filtros de cociente. Esos filtros aproximan para cada componente qué elementos están almacenados en él. Los árboles LSM se utilizan en bases de datos como Apache AsterixDB, Bigtable , HBase , LevelDB , SQLite4 .
Las redes ofrecen muchas aplicaciones para los filtros AMQ. Se utilizan para aproximar un conjunto de datos que se encuentran en servidores diferentes. En muchos casos, esos filtros AMQ pueden considerarse inmutables. Incluso si el conjunto en el servidor remoto cambia, el filtro AMQ a menudo no se actualiza de inmediato, pero se toleran algunos falsos positivos. Un ejemplo de esta aplicación es el uso compartido de caché web. Si un proxy tiene un error de caché, desea determinar si otro proxy tiene los datos solicitados. Por lo tanto, el proxy debe saber o al menos aproximarse si otro proxy tiene la página web solicitada. Esto se puede lograr mediante la difusión periódica de un filtro AMQ estático de las URL de las páginas web que un proxy ha almacenado en caché en lugar de difundir listas de URL. En esta configuración, pueden producirse falsos negativos si la caché cambia entre actualizaciones periódicas.
El mismo concepto se puede aplicar a las redes P2P. Los filtros AMQ se pueden utilizar para aproximar lo que está almacenado en cada nodo de la red. El filtro se puede rellenar con identificadores o palabras clave de los documentos reales de los nodos. Los falsos positivos solo conducen a algunas solicitudes innecesarias. Los filtros AMQ tienen otras aplicaciones en las redes P2P, por ejemplo, para encontrar la diferencia o intersección entre conjuntos almacenados en diferentes nodos.
