¿Cómo funcionan los filtros de escalamiento escalables?

Déjame intentar darle una oportunidad a esto para ver cuánto puedo matarlo. :-)

Entonces, para comenzar, debe poder crear un filtro de floración regular que permita un número finito de elementos con una probabilidad máxima de un falso positivo. Se requiere la adición de estas características a su filtro básico antes de intentar construir una implementación escalable.

Antes de que intentemos controlar y optimizar cuál es la probabilidad, podemos determinar cuál es la probabilidad para un tamaño de filtro de floración dado.

Primero dividimos el campo de bits según la cantidad de funciones hash (número total de bits / número de funciones hash = segmentos) para obtener k segmentos de bits que representan cada función hash, de modo que k bits siempre describe cada elemento.

Si aumenta el número de segmentos o el número de bits por segmento, la probabilidad de falsos positivos disminuirá.

También se deduce que a medida que se agregan elementos, más bits se establecen en 1, por lo que aumentan los falsos positivos. Nos referimos a esto como la "proporción de relleno" de cada sector.

Cuando el filtro contiene una gran cantidad de datos, podemos suponer que la probabilidad de falsos positivos para este filtro es la proporción de relleno elevada al número de segmentos (si tuviéramos que contar los bits en lugar de utilizar una relación, esto se simplifica en una permutación con problema de repetición).

Entonces, ¿cómo podemos averiguar cómo elegir una probabilidad de falsos positivos en un filtro de floración? Podemos modificar la cantidad de segmentos (que afectarán la proporción de relleno).

Para averiguar cuántas rebanadas deberíamos tener, comenzamos por averiguar la proporción de relleno óptima para una rebanada. Dado que la proporción de relleno se determina por el número de bits en un segmento que son 1 versus el número de bits que son 0, podemos determinar que cada bit permanecerá sin establecer con probabilidad de (100% - (1 / bits en un segmento) ). Ya que vamos a tener varios elementos insertados, tenemos otra permutación con problemas de reputación y expandimos los elementos a la proporción de relleno esperada, que es (100% - ((100% - (1 / bits en una porción)) ^ "elementos insertados")). Bueno, resulta que esto es muy similar a otra ecuación. En el documento, relacionan la proporción de relleno con otra ecuación, por lo que encaja perfectamente en una serie de taylor (1-e ^ (- n / m)). Después de un poco de esfuerzo con esto, resulta que la proporción de relleno óptima es siempre alrededor del 50%, independientemente de cualquiera de las variables que cambies.

Entonces, como la probabilidad de un filtro es la proporción de relleno elevada al número de cortes, podemos completar el 50% y obtener P = (50%) ^ k o k = log_2 (1 / P). Luego podemos usar esta función para calcular la cantidad de segmentos que deberíamos generar para un filtro dado en la lista de filtros para un filtro de floración escalable.

    def slices_count(false_positive_probability):
        return math.ceil(math.log(1 / false_positive_probability, 2))

Editar: Después de escribir esto, encontré una mención de la "regla del cincuenta por ciento" al leer sobre la asignación de memoria dinámica basada en el sistema Buddy en TAoCP Vol 1, pp 442-445 con un razonamiento mucho más limpio versus ajuste de la curva a (1-e ^ (- n / m)). Knuth también hace referencia a un documento "La regla del cincuenta por ciento revisado" con un poco de antecedentes sobre el concepto ( pdf disponible aquí ).

Un elemento está en el filtro de floración escalable si algún filtro devuelve verdadero. Por lo tanto, puede agregar filtros sin afectar las consultas de membresía para elementos anteriores.

Para asegurarse de que todavía tiene una garantía de falsos positivos en el peor de los casos, se agregan nuevos filtros con tasas de falsos positivos que disminuyen geométricamente. Por ejemplo, el primer filtro tiene una tasa de falsos positivos p , el segundo rp , el tercer r^2p , etc. La probabilidad de un falso positivo sobre el filtro de floración escalable está limitada por el enlace de unión: sum_{k>=0} r^k p = p/(1-r) .

  

Estaba leyendo sobre filtros de floración escalables y no podía entender cómo cada vez que se llena un filtro de floración constituyente, se agrega un nuevo filtro de floración con un tamaño más grande.
  Los elementos que contribuyeron al conjunto de bits en los filtros creados inicialmente no pueden ser buscados por presencia. Tal vez me equivoque al entender esto?

Hola,
La idea básica es agregar al primer filtro hasta que el campo de bits del primer filtro de nivel esté saturado. Estar saturado significa no que se usa cada bit, pero significa que el filtro contiene tantas entradas que las entradas adicionales crearían demasiados falsos positivos.

Desde el punto de saturación, cualquier elemento nuevo no se agregará al filtro saturado, sino a un sub-filtro nuevo y más grande (el filtro de segundo nivel).

Para encontrar un valor, lo buscará en el filtro de primer nivel, y si no lo encuentra allí, lo buscará en el filtro de segundo nivel. Si puede encontrarlo en cualquiera de estos filtros, es (por una buena posibilidad) "conocido" por el filtro (los falsos positivos pueden ocurrir como resultado de la naturaleza de los filtros Bloom). Si no puede encontrar el valor en ninguno de los filtros, se garantiza que el filtro no lo ha visto. Esto, por supuesto, puede expresarse como una estructura de datos recursiva.

Es posible que desee leer la publicación de mi blog que contiene una implementación de filtro Bloom escalable en Java y una explicación de cómo funciona en detalle.