¿Cuándo es útil un filtro Bloom?

Question

Entiendo lo que hace que los filtros de bloom sean una estructura de datos atractiva; sin embargo, me resulta difícil comprender realmente cuándo puede usarlos, ya que todavía tiene que realizar la costosa operación que está tratando de evitar para asegurarse de que no ha encontrado un falso positivo. Debido a esto, ¿no agregarían muchos gastos generales? Por ejemplo, el artículo de Wikipedia para filtros de bloom sugiere que se pueden usar para la sincronización de datos. Veo cómo sería genial la primera vez cuando el filtro de floración está vacío, pero di que no has cambiado nada y vas a sincronizar tus datos nuevamente. Ahora, cada búsqueda en el filtro de bloom informará que el archivo ya se ha copiado, pero ¿no tendríamos que realizar otra vez la tarea de búsqueda más lenta que intentamos evitar para asegurarnos de que es correcto?

Answer 1

Básicamente, usa filtros Bloom para evitar la larga y ardua tarea de probar que un elemento no existe en la estructura de datos. Es casi siempre más difícil determinar si falta algo que si existe, por lo que el filtro ayuda a apuntalar las pérdidas buscando cosas que de todos modos no encontrarás. No siempre funciona, pero cuando lo hace, obtiene un gran beneficio.

Answer 2

Los filtros Bloom son muy eficientes en el caso de consultas de membresía, es decir, para saber si un elemento pertenece al conjunto. La cantidad de elementos en el conjunto no afecta el rendimiento de la consulta.