Hispanopedia Wiki
Articulo de referencia

Filtro de consulta de membresía aproximada

Los filtros de consulta de pertenencia aproximada (en adelante, filtros AMQ) comprenden un grupo de estructuras de datos probabilísticas eficientes en espacio que admiten consul...

Hispanopedia WikiContenido en espanolLectura gratuita

Los filtros de consulta de pertenencia aproximada (en adelante, filtros AMQ) comprenden un grupo de estructuras de datos probabilísticas eficientes en espacio 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ϵ{\displaystyle \epsilon }.

Los filtros Bloom son el tipo de filtro AMQ más conocido, 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. En estos entornos, se utilizan con frecuencia para evitar solicitudes de red u operaciones de entrada/salida que resulten de la solicitud de elementos inexistentes.

Problema de consulta de membresía aproximada

El problema de consulta de pertenencia aproximada consiste en almacenar información sobre un conjunto de elementos S de forma eficiente en cuanto al espacio. El objetivo es responder a consultas sobre si un elemento x pertenece o no al conjunto S , limitando los falsos positivos a una probabilidad máxima.ϵ{\displaystyle \epsilon }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 la eliminación de elementos o la fusión de dos filtros.

Buscar

Una consulta de filtro AMQ determinará si un elemento definitivamente no está en el conjunto o si probablemente sí lo está.

En otras palabras, si el filtro representa un conjunto S y estamos interesados ​​en un valor s , entonces la función de búsqueda aplicada a s se comporta de la siguiente manera:

  • sis∈S{\displaystyle s\in S}: siempre devuelve verdadero.
  • sis∉S{\displaystyle s\notin S}: devuelve falso con probabilidad1−ϵ{\displaystyle 1-\epsilon }.

Un falso positivo es una búsqueda de un elemento que no forma parte del conjunto, pero donde la búsqueda devuelve verdadero. La probabilidad de que esto ocurra es la tasa de falsos positivos.ϵ{\displaystyle \epsilon }Los filtros AMQ no permiten falsos negativos (la búsqueda devuelve falso aunque el elemento forme parte del conjunto).

Inserción

Tras insertar un elemento, la búsqueda de dicho elemento debe devolver verdadero. Los filtros AMQ dinámicos permiten insertar elementos uno a uno sin reconstruir la estructura de datos . Otros filtros AMQ deben reconstruirse después de cada inserción. Estos se denominan filtros AMQ estáticos.

Tasa de falsos positivos frente al espacio

Existe una relación de compromiso entre el tamaño del almacenamiento y la tasa de falsos positivos.ϵ{\displaystyle \epsilon }. Aumentar el espacio de almacenamiento reduce la tasa de falsos positivos. El límite inferior teórico esregistro2⁡(1/ϵ){\displaystyle \log _{2}(1/\epsilon )}bits para cada elemento. [ 1 ] Los filtros AMQ dinámicos no pueden alcanzar este límite inferior. Necesitan al menosnorteregistro2⁡(1/ϵ)(1+o(1)){\displaystyle n\log _{2}(1/\epsilon )(1+o(1))}piezas paranorte{\displaystyle n}inserciones. [ 2 ] Los distintos filtros AMQ tienen diferentes rangos de tasas de falsos positivos y requisitos de espacio. Elegir el mejor filtro AMQ depende de la aplicación.

Resultados teóricos e historial del problema

Los filtros AMQ fueron introducidos por primera vez en 1970 por Bloom, [ 3 ] quien introdujo el filtro Bloom y demostró que utiliza espacio≈1.44norteregistro2⁡ϵ−1{\displaystyle \approx 1.44n\log _{2}\epsilon ^{-1}}bits de espacio. En 1978, Carter demostró que el espacio óptimo para un filtro estático se encuentra entrenorteregistro2⁡ϵ−1{\displaystyle n\log _{2}\epsilon ^{-1}}ynorteregistro2⁡ϵ−1+o(norte){\displaystyle n\log _{2}\epsilon ^{-1}+o(n)}bits, e introdujo la técnica algorítmica de construir un filtro almacenando una colección de huellas digitales (hashes de las claves) en una tabla hash compacta o concisa. Dichos filtros a veces se denominan filtros de huellas digitales, [ 4 ] [ 5 ] e incluyen construcciones prácticas modernas como los filtros de cociente y los filtros cuco .

En 2005, Pagh, Pagh y Srinivasa [ 6 ] mostraron cómo construir un filtro de huella digital de tiempo constante utilizando espacio(1+o(1))norteregistro2⁡ϵ−1+O(norte){\displaystyle (1+o(1))n\log _ {2}\epsilon ^{-1}+O(n)}bits de espacio. En 2021, Bender, Farach-Colton, Kuszmaul, Kuszmaul y Liu [ 4 ] construyeron un filtro de huellas dactilares de tiempo constante utilizando espacionorteregistro2⁡ϵ−1+norteregistro2⁡mi+o(norte){\displaystyle n\log _{2}\epsilon ^{-1}+n\log _{2}e+o(n)}bits, siempre y cuandoregistro⁡ϵ−1∈ω(1)∩O(registro⁡norte/registro⁡registro⁡norte){\displaystyle \log \epsilon ^{-1}\in \omega (1)\cap O(\log n/\log \log n)}. Posteriormente se demostró que este límite era óptimo desde el punto de vista de la teoría de la información [ 5 ] para cualquier filtro dinámico (cualquier filtro que admita inserciones y eliminaciones), independientemente de la complejidad temporal .

Para los filtros que solo admiten inserciones, se ha demostrado que el límite de espacio óptimo desde el punto de vista de la teoría de la información esnorteregistro2⁡ϵ−1+Θ(norte){\displaystyle n\log _{2}\epsilon ^{-1}+\Theta (n)}cuandoϵ=Θ(1){\displaystyle \epsilon =\Theta (1)}, ynorteregistro2⁡ϵ−1+o(norte){\displaystyle n\log _{2}\epsilon ^{-1}+o(n)}cuandoϵ=o(1){\displaystyle \epsilon =o(1)}. [ 7 ] [ 8 ] Para filtros estáticos, donde no se permiten inserciones/eliminaciones, existe un compromiso entre el tiempo de consulta y el espacio, con límites superiores e inferiores coincidentes debido a Hu et al. [ 9 ] Para filtros que crecen con el tiempo, connorte{\displaystyle n}definido como el número actual de claves en un momento dado, el límite de espacio óptimo esnorteregistro2⁡ϵ−1+Θ(norteregistro⁡registro⁡norte){\displaystyle n\log _{2}\epsilon ^{-1}+\Theta (n\log \log n)}bits. [ 10 ]

Estructuras de datos

Existen diferentes maneras de resolver el problema de la consulta de pertenencia aproximada. La estructura de datos más conocida son los filtros de Bloom , pero existen otras estructuras de datos que ofrecen un mejor rendimiento en cuanto a tasas de falsos positivos y requisitos de espacio, admiten operaciones adicionales o presentan tiempos de inserción y búsqueda diferentes. A continuación, describimos algunos filtros AMQ conocidos.

Filtro Bloom

Un filtro Bloom es una matriz de bits demetro{\displaystyle m}piezas conk{\displaystyle k}funciones hash. Cada función hash asigna un elemento a una de lasmetro{\displaystyle m}posiciones en el array. Al principio, todos los bits del array se establecen a cero. Para insertar un elemento, se calculan todas las funciones hash y todos los bits correspondientes en el array se establecen a uno. Para buscar un elemento, todosk{\displaystyle k}Se calculan las funciones hash. Si todos los bits correspondientes están activados, truese devuelve. Para reducir la tasa de falsos positivos, el número de funciones hash ymetro{\displaystyle m}puede aumentarse.

Filtro de cociente

La idea de los filtros de cociente es aplicar un hash a un elemento y dividir su huella digital enr{\displaystyle r}los bits menos significativos se denominan restodR{\displaystyle d_{R}}y las partes más significativas llamadas cocientedQ{\displaystyle d_{Q}}El cociente determina dónde se almacena el resto en la tabla hash . Se utilizan tres bits adicionales por cada ranura en la tabla hash para resolver colisiones suaves (mismo cociente pero diferentes restos).

Filtro de cuco

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 posibles ubicaciones. La segunda ubicación se calcula a partir de la primera y la huella digital del elemento. Esto es necesario para permitir el movimiento de elementos ya insertados si ambas ranuras posibles para un elemento están ocupadas.

Tras alcanzar un umbral de carga, la velocidad de inserción del filtro Cuckoo disminuye. Es posible que se produzca un fallo en la inserción y que sea necesario recalcular el hash de la tabla.

Filtro XOR

Los filtros XOR [ 11 ] son ​​filtros AMQ estáticos que se basan en un filtro Bloomier y utilizan la idea de tablas hash perfectas . De forma similar a los filtros Cuckoo, guardan huellas digitales de los elementos en una tabla hash. La idea es que una consulta para un elementoincógnita{\displaystyle x}es verdadero si la operación XOR de tres funciones hash dadash0,h1,h2{\displaystyle h_{0},h_{1},h_{2}}es la huella digital de incógnita{\displaystyle x}Al construir la tabla hash, a cada elemento se le asigna una de sus tres ranuras de manera que ningún otro elemento se asigne a esa ranura. Después de que todos los elementos se hayan asignado, establecemos para cada elemento el valor de su ranura como el XOR de las otras dos ranuras (no asignadas) del elemento y la huella digital del elemento. Este algoritmo de construcción puede fallar de tal manera que no sean posibles las inserciones dinámicas sin reconstruir la tabla hash. Esta tabla hash se puede construir utilizando solo1.23registro2⁡(1/ϵ){\displaystyle 1.23\log _{2}(1/\epsilon )}bits por elemento.

La desventaja de este filtro es que la estructura de datos debe reconstruirse si se añaden elementos adicionales. Se utilizan en aplicaciones donde no es necesario añadir elementos posteriormente y el espacio es limitado.

Solicitud

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 para el conjunto de claves de una base de datos o memoria remota. Antes de realizar una consulta, presumiblemente lenta, a la base de datos o a la memoria remota, el filtro AMQ se utiliza para proporcionar una respuesta aproximada sobre si la clave se encuentra 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 es de esperar que sea poco frecuente) se realiza una operación de E/S o un acceso remoto innecesario. Las aplicaciones son numerosas e incluyen el enrutamiento de paquetes y recursos, redes P2P y almacenamiento en caché distribuido. [ 12 ]

Los filtros AMQ se utilizan a menudo como estructura de datos en memoria para evitar costosos accesos al disco. Una aplicación son los árboles de fusión estructurados por registros (LSM). Estos árboles tienen un componente rápido en memoria y uno o varios componentes en disco que también son árboles. Los elementos se insertan en el componente en memoria hasta que alcanza su tamaño máximo, momento en el que se fusiona con los componentes en disco. Para acelerar la búsqueda, muchos árboles LSM implementan filtros AMQ, como filtros Bloom o filtros de cociente. Estos 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 y SQLite4 .

Las redes ofrecen numerosas aplicaciones para los filtros AMQ. Se utilizan para aproximar un conjunto de datos ubicado en distintos servidores. En muchos casos, estos filtros AMQ pueden considerarse inmutables. Incluso si el conjunto de datos en el servidor remoto cambia, el filtro AMQ no suele actualizarse de inmediato, aunque se toleran algunos falsos positivos. Un ejemplo de esta aplicación es el uso compartido de la caché web . Si un proxy no encuentra los datos en la caché, necesita determinar si otro proxy dispone de la información solicitada. Por lo tanto, el proxy debe saber, o al menos aproximar, si otro proxy contiene la página web solicitada. Esto se puede lograr mediante la difusión periódica de un filtro AMQ estático con las URL de las páginas web que un proxy tiene en caché, en lugar de difundir listas de URL. En este caso, pueden producirse falsos negativos si la caché cambia entre las actualizaciones periódicas.

El mismo concepto se puede aplicar a las redes P2P. Los filtros AMQ permiten aproximar el contenido 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 generan solicitudes innecesarias. Los filtros AMQ tienen otras aplicaciones en redes P2P, como por ejemplo, encontrar las diferencias o intersecciones entre conjuntos almacenados en distintos nodos.

Véase también

Referencias

  1. ↑ Carter; Larry (1978). "Probadores de pertenencia exactos y aproximados" . Actas del décimo simposio anual de la ACM sobre Teoría de la Computación - STOC '78 . págs. 59–65 . doi : 10.1145/800133.804332 . S2CID 6465743 .  
  2. ↑ Lovett; Shachar (2010). "Un límite inferior para estructuras de datos de pertenencia aproximada dinámica". 2010 IEEE 51st Annual Symposium on Foundations of Computer Science . pp. 797–804 . doi : 10.1109/FOCS.2010.81 . ISBN  978-1-4244-8525-3. S2CID 7904735 . 
  3. ↑ Bloom, Burton H. (1970). "Compromisos espacio/tiempo en la codificación hash con errores permitidos" . Communications of the ACM . 13 (7): 422– 426. doi : 10.1145/362686.362692 . ISSN 0001-0782 . 
  4. 1 2 Bender, Michael A.; Farach-Colton, Martín; Kuszmaul, John; Kuszmaul, William; Liu, Mingmou (2022-06-09). "Sobre la compensación óptima tiempo/espacio para tablas hash" . Actas del 54.º Simposio Anual ACM SIGACT sobre Teoría de la Computación . Nueva York, NY, EE. UU.: ACM. págs. 1284–1297 . doi : 10.1145/3519935.3519969 . hdl : 1721.1/146419 . ISBN  978-1-4503-9264-8.
  5. 1 2 Kuszmaul, William; Liang, Jingxun; Zhou, Renfei (14 de diciembre de 2025). "Los filtros de huella digital son óptimos" . 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. pp. 1059–1073 . doi : 10.1109/focs63196.2025.00055 . ISBN  979-8-3315-7132-0.
  6. ↑ Pagh, Anna; Pagh, Rasmus; Rao, Srinivasa (2005). "Un reemplazo óptimo del filtro de Bloom" . Actas del decimosexto simposio anual ACM-SIAM sobre algoritmos discretos . Sociedad de Matemáticas Industriales y Aplicadas. págs. 823–829 . ISBN  978-0-89871-585-9.
  7. ↑ Lovett, Shachar; Porat, Ely (2013). "Un límite inferior de espacio para estructuras de datos de pertenencia aproximada dinámica" . SIAM Journal on Computing . 42 (6): 2182– 2196. doi : 10.1137/120867044 . ISSN 0097-5397 . 
  8. ↑ Kuszmaul, William; Walzer, Stefan (10 de junio de 2024). «Límites inferiores del espacio para filtros dinámicos y recuperación dinámica de valores». Actas del 56.º Simposio Anual de la ACM sobre Teoría de la Computación . Nueva York, NY, EE. UU.: ACM. págs. 1153–1164 . doi : 10.1145/3618260.3649649 . ISBN  979-8-4007-0383-6.
  9. ↑ Hu, Yang; Kuszmaul, William; Liang, Jingxun; Yu, Huacheng; Zhang, Junkai; Zhou, Renfei (14 de diciembre de 2025). "Recuperación estática revisada: hacia la optimalidad y más allá" . 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. págs. 2392–2409 . doi : 10.1109/focs63196.2025.00126 . ISBN  979-8-3315-7132-0.
  10. ↑ Pagh, Rasmus; Segev, Gil; Wieder, Udi (2013). "Cómo aproximar un conjunto sin conocer su tamaño de antemano" . 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . IEEE. pp. 80–89 . Bibcode : 2013sfcs.conf...19P . doi : 10.1109/focs.2013.17 . ISBN  978-0-7695-5135-7.
  11. ↑ Graf; Lemire (2020). "Filtros XOR". ACM Journal of Experimental Algorithmics . 25 : 1–16 . arXiv : 1912.08258 . doi : 10.1145/3376122 . S2CID 209405019 . 
  12. ↑ Broder, Andrei; Mitzenmacher, Michael (2002). "Aplicaciones de redes de filtros de Bloom: una revisión". Internet Mathematics : 636–646 . CiteSeerX 10.1.1.20.98 .