¿Hay un filtro anti-Bloom?

25

Un filtro Bloom permite realizar un seguimiento eficiente de si ya se han encontrado varios valores durante el procesamiento. Cuando hay muchos elementos de datos, un filtro Bloom puede generar un ahorro significativo de memoria en una tabla hash. La característica principal de un filtro Bloom, que comparte con una tabla hash, es que siempre dice "no nuevo" si un elemento no es nuevo, pero hay una probabilidad distinta de cero de que un elemento se marque como "no nuevo" "incluso cuando es nuevo.

¿Existe un "filtro anti-Bloom" que tenga el comportamiento opuesto?

En otras palabras: ¿existe una estructura de datos eficiente que diga "nuevo" si un elemento es nuevo, pero que también podría decir "nuevo" para algunos elementos que no son nuevos?

Mantener todos los elementos vistos anteriormente (por ejemplo, en una lista vinculada ordenada) satisface el primer requisito pero puede usar mucha memoria. Espero que también sea innecesario, dado el segundo requisito relajado.


Para aquellos que prefieren un tratamiento más formal, escriba si el filtro Bloom cree que es nuevo, contrario, y escriba si realmente es nuevo contrario.b(x)=1xb(x)=0n(x)=1xn(x)=0

Entonces ; ; ; , para algunos .Pr[b(x)=0|n(x)=0]=1Pr[b(x)=0|n(x)=1]=αPr[b(x)=1|n(x)=0]=0Pr[b(x)=1|n(x)=1]=1α0<α<1

Estoy preguntando: ¿existe una estructura de datos eficiente, implementando una función con algún , tal que ; ; ; ?b0<β<1Pr[b(x)=0|n(x)=0]=βPr[b(x)=0|n(x)=1]=0P r [ b ( x ) = 1 | n ( x ) = 1 ] = 1Pr[b(x)=1|n(x)=0]=1βPr[b(x)=1|n(x)=1]=1


Editar: Parece que esta pregunta se ha hecho antes en StackExchange, ya que /programming/635728 y /cstheory/6596 con un rango de respuestas de "no se puede hecho "a través" se puede hacer, a algún costo "a" es trivial, invirtiendo los valores de ". Todavía no me queda claro cuál es la respuesta "correcta". Lo que está claro es que un esquema de almacenamiento en caché LRU de algún tipo (como el sugerido por Ilmari Karonen) funciona bastante bien, es fácil de implementar y resultó en una reducción del 50% en el tiempo necesario para ejecutar mi código.b

András Salamon
fuente
Por alguna razón, me siento tentado a decir que esto es muy similar al problema que los cachés y los algoritmos de colocación de caché intentan resolver. Considere una memoria caché utilizando el reemplazo menos utilizado (LFU). Un algoritmo de reemplazo teóricamente óptimo pero imposible sería desalojar el que no volverá a ver durante mucho tiempo, al igual que para los cachés. Supongo que el almacenamiento en caché se basa en algunas suposiciones sobre la naturaleza de la distribución que generalmente no se mantienen, pero vale la pena considerar si esto se aplica.
Patrick87
Te puede interesar la siguiente charla: Filtros de membresía basados
Kaveh
@Kaveh: gracias por el puntero, mirará.
András Salamon

Respuestas:

12

De acuerdo con la idea hash de Patrick87, aquí hay una construcción práctica que casi cumple con sus requisitos: la probabilidad de confundir falsamente un valor nuevo con uno antiguo no es del todo cero, pero puede hacerse fácilmente insignificante.

Elija los parámetros y ; valores prácticos podrían ser, por ejemplo, y . Sea una función hash criptográfica segura que produce (al menos) bits de salida.k n = 128 k = 16 H n + knkn=128k=16Hn+k

Vamos ser una matriz de bitstrings -bit. Esta matriz almacena el estado del filtro, utilizando un total de bits. (No importa en particular cómo se inicializa esta matriz; solo podemos llenarla con ceros o con bits aleatorios).2 k n n 2 ka2k nn2k

  • Para agregar un nuevo valor al filtro, calcule , donde denota los primeros bits y denota los siguientes bits de . Deje .xi k j n H ( x ) a i = jij=H(x)ikjnH(x)ai=j

  • Para probar si se ha agregado un valor al filtro, calcule , como se indica arriba, y verifique si . Si es así, devuelve verdadero; de lo contrario, devuelve falso.i xa i = j ij=H(x)ai=j

Reclamación 1: la probabilidad de un falso positivo (= nuevo valor que se afirma haber visto falsamente) es . Esto puede hacerse arbitrariamente pequeño, a un costo modesto en el espacio de almacenamiento, aumentando ; en particular, para , esta probabilidad es esencialmente insignificante, siendo, en la práctica, mucho menor que la probabilidad de un falso positivo debido a un mal funcionamiento del hardware. n n 1281/2n+knn128

En particular, después de que se hayan verificado y agregado al filtro valores distintos, la probabilidad de que haya ocurrido al menos un falso positivo es . Por ejemplo, con y , el número de valores distintos necesarias para conseguir un falso positivo con 50% de probabilidad es de aproximadamente .( N 2 - N ) / 2 n + k + 1 n = 128 k = 16N(N2N)/2n+k+1n=128k=162(n+k)/2=272

Reclamación 2: La probabilidad de un falso negativo (= valor agregado previamente que se afirma falsamente como nuevo) no es mayor que , donde es el número de valores distintos agregados al filtro (o, más específicamente, el número de valores distintos agregados después de que el valor específico que se está probando se haya agregado más recientemente al filtro).1(12k)N1exp(N/2k)<N/2kN


PD. Para poner en perspectiva "insignificantemente pequeño", el cifrado de 128 bits generalmente se considera indescifrable con la tecnología actualmente conocida. Obtener un falso positivo de este esquema con es tan probable como que alguien adivine correctamente su clave secreta de cifrado de 128 bits en su primer intento . (Con y , que es en realidad cerca de 65.000 veces menos probable que eso.)n+k=128n=128k=16

Pero si eso todavía te hace sentir irracionalmente nervioso, siempre puedes cambiar a ; que va a duplicar sus requisitos de almacenamiento, pero con seguridad se puede apostar cualquier suma que le importa a nombre de que nadie va nunca ver a un falso positivo con - suponiendo que la función hash no se rompe, de todos modos.n=256n=256

Ilmari Karonen
fuente
1
No solo se puede hacer que la probabilidad sea comparable a la del mal funcionamiento del hardware; también se puede comparar con la probabilidad de que alguien adivine su clave RSA para iniciar sesión SSH en el primer intento . En mi opinión, este último transmite la practicidad de su solución más que el primero.
R ..
+1 Muy bueno, entiendo que esto resuelve el problema de eficiencia de espacio al permitir alguna posibilidad (muy pequeña) de responder incorrectamente "no nuevo" cuando el elemento es, de hecho, nuevo. Muy práctico y buen análisis.
Patrick87
1
La reivindicación 1 solo indica que una función hash decente tiene una baja probabilidad de colisiones. Esto ya es cierto en la práctica si es al menos 50 más o menos. Para mi aplicación, y funciona muy bien con un simple de 64 bits, no criptográficamente seguro, pero función hash rápido. n = 44 k = 20n+kn=44k=20
András Salamon
@ AndrásSalamon: Cierto, aunque una función hash criptográfica segura en realidad proporciona una garantía un poco más fuerte: a saber, que no es práctico encontrar entradas en colisión, incluso si intenta buscarlas deliberadamente . Con un suficientemente grande (por ejemplo, como sugerí anteriormente), esto significa que el almacenamiento de los datos completos es innecesario incluso si el costo de un falso positivo es alto e incluso si puede haber un adversario activo intentando encontrar uno. Por supuesto, si no necesita una garantía tan sólida, puede ser aceptable un riesgo de colisión algo mayor. n = 128nn=128
Ilmari Karonen
1
@Newtopian La razón por la que especifiqué una función hash criptográfica es que, para aquellos, no existe una forma conocida de generar colisiones de manera más efectiva que por la fuerza bruta (es decir, probando muchas entradas y seleccionando las que colisionan), o de lo contrario se consideraría el hash roto (como, digamos, MD5 hoy en día está). Por lo tanto, para un hash criptográfico, podemos suponer con bastante seguridad que la tasa de colisión es la misma que para una función hash aleatoria ideal. El uso de una función hash universal o un MAC con clave (con una clave secreta aleatoria) haría que esta garantía sea aún más fuerte.
Ilmari Karonen
8

No, no es posible tener una estructura de datos eficiente con estas propiedades, si desea tener una garantía de que la estructura de datos dirá "nuevo" si es realmente nuevo (nunca, nunca dirá "no nuevo" si de hecho es nuevo; no se permiten falsos negativos). Cualquier estructura de datos de este tipo deberá conservar todos los datos para responder "no nuevo". Vea la respuesta de pents90 en teoría para una justificación precisa.

En contraste, los filtros Bloom pueden garantizar que la estructura de datos dirá "no nuevo" si no es nuevo, de manera eficiente. En particular, los filtros Bloom pueden ser más eficientes que almacenar todos los datos: cada elemento individual puede ser bastante largo, pero el tamaño del filtro Bloom se escala con el número de elementos, no su longitud total. Cualquier estructura de datos para su problema tendrá que escalar con la longitud total de los datos, no con el número de elementos de datos.

jbapple
fuente
También vea la respuesta aceptada, ya que la pregunta es la misma
Joe
-1 Probablemente deberías calificar lo que quieres decir cuando dices que no es posible. Claramente, es posible hacerlo de manera eficiente, y también es posible hacerlo con una baja tasa de error, por lo que alcanzar un cierto equilibrio en una implementación dada debería ser factible ... en particular, sería útil explicar exactamente qué se entiende por "todos los datos", ya que esto no es estrictamente necesario para satisfacer la pregunta formulada. Los falsos negativos, que responden "nuevo" cuando la respuesta debería ser "no nueva", están permitidos aquí, por lo que no todos los datos deben conservarse.
Patrick87
1
Esta respuesta es perfectamente razonable y parece abordar la letra de mi pregunta, pero quizás no el espíritu.
András Salamon
@DW Gracias por tomarse el tiempo para actualizar la respuesta. Me inclino a dejar esto como respuesta ahora, aunque todavía me opongo al lenguaje utilizado al describir la ineficiencia de los filtros anti-floración, además de pensar que sería mejor elaborar un poco más sobre los "detalles" a los que se hace referencia. .. dejando el -1 por ahora. Limpió algunos comentarios obsoletos.
Patrick87
@DW Por "falso negativo", pretendo responder "nuevo" cuando la respuesta debería haber sido "no nueva". (Algo contradictorio, "no es nuevo" es el caso positivo aquí.) No es necesario guardar "todos los datos nunca" para lograr esto, aunque me inclino a creer que necesita guardar elementos completos (solo no todos los elementos, a menos que esté dispuesto a aceptar una posibilidad de error hipotéticamente significativa, según la otra respuesta a la pregunta aquí.)
Patrick87
6

¿Qué tal solo una tabla hash? Cuando vea un nuevo elemento, consulte la tabla hash. Si el lugar del elemento está vacío, devuelva "nuevo" y agregue el elemento. De lo contrario, verifique si el lugar del artículo está ocupado por el artículo. Si es así, devuelve "no nuevo". Si el lugar está ocupado por algún otro elemento, devuelva "nuevo" y sobrescriba el lugar con el nuevo elemento.

Definitivamente siempre obtendrá correctamente "Nuevo" si nunca antes ha visto el hash del elemento. Definitivamente siempre obtendrá correctamente "No nuevo" si solo ha visto el hash del elemento cuando ha visto el mismo elemento. La única vez que obtendrá "Nuevo" cuando la respuesta correcta sea "No nuevo" es si ve el elemento A, luego ve el elemento B, luego ve el elemento A nuevamente, y tanto A como B hacen lo mismo. Es importante destacar que nunca puede obtener "No nuevo" incorrectamente.

Patrick87
fuente
1
Supongo que esto ignora el problema de la eficiencia del espacio, o más bien, es significativamente menos eficiente de lo que sería un filtro de floración, ya que un filtro de floración realmente solo necesita un poco por cubo, y esto necesita tanto espacio por cubo como espacio para Representa los artículos. Oh, bueno ... a menos que el universo sea finito (como en la respuesta de Wandering Logic) creo que probablemente no puedas acercarte mucho a la eficiencia espacial de un filtro de floración.
Patrick87
Personalmente, creo que tu respuesta es mucho mejor que la mía. Un filtro de floración no es solo un poco por cubeta si desea probabilidades superiores al 50%. También es un tamaño fijo y una vez que lo llena más de la mitad, la probabilidad de falsos positivos aumenta precipitadamente. No hay una forma conveniente de expandirlo, no hay una manera conveniente de usarlo como caché y no hay una forma conveniente de eliminar elementos. Tomaré una tabla hash cada vez.
Wandering Logic
@WanderingLogic El uso de un pequeño contador de saturación en lugar de un solo bit permite la eliminación (a costa de la capacidad y solo si el contador no está al máximo, obviamente).
Paul A. Clayton
4

En el caso donde el universo de elementos es finito, entonces sí: solo use un filtro de floración que registre qué elementos están fuera del conjunto, en lugar de en el conjunto. (Es decir, use un filtro de floración que represente el complemento del conjunto de interés).

Un lugar donde esto es útil es permitir una forma limitada de eliminación. Tienes dos filtros de floración. Comienzan vacíos. A medida que inserta elementos, los inserta en el filtro de floración A. Si luego desea eliminar un elemento, inserte ese elemento en el filtro de floración B. No hay forma de recuperarlo. Para realizar una búsqueda, primero busque en el filtro de floración A. Si no encuentra ninguna coincidencia, el elemento nunca se insertó (con probabilidad 1). Si encuentra una coincidencia, el elemento puede (o no) haber sido insertado. En ese caso, realice una búsqueda en el filtro de floración B. Si no encuentra ninguna coincidencia, el elemento nunca se eliminó. Si encuentra una coincidencia en el filtro de floración B, el elemento probablemente se insertó y luego se eliminó.

Esto realmente no responde a su pregunta, pero, en este caso limitado, el filtro de floración B está realizando exactamente el comportamiento de "filtro anti-floración" que está buscando.

Los investigadores del filtro Real Bloom utilizan formas mucho más eficientes de representar la eliminación, consulte la página de publicación de Mike Mitzenmacher .

Lógica Errante
fuente
En esta pregunta, estamos procesando elementos y no hay eliminaciones. No hay una manera significativa de almacenar el cumplido sin tener que quitar elementos del filtro de floración
Joe
1
@ Joe: Estoy de acuerdo en que el problema es insoluble en general, por lo que restringí mi respuesta al caso donde el complemento era finito y pequeño.
Wandering Logic
1

Solo quiero agregar aquí, que si estás en una situación afortunada, conoces todos los valores que posiblemente puedas ver; entonces puedes usar un filtro de recuento de floración.vi

Un ejemplo podría ser las direcciones IP, y desea saber cada vez que aparece una que nunca ha visto antes. Pero todavía es un conjunto finito, por lo que sabes lo que puedes esperar.

La solución real es simple:

  1. Agregue todos sus artículos al filtro de recuento de floración.
  2. Cuando vea un nuevo elemento, tendrá valores en todos los espacios.1
  3. Después de ver un elemento nuevo real, restarlo del filtro.

Por lo tanto, es posible que tenga valores de 'falsos positivos' que en realidad eran viejos, pero reconocidos como nuevos. Sin embargo, nunca obtendrá 'no nuevo' para un nuevo valor, ya que su valor seguirá estando en todas las ranuras, y nadie más podría haberlo quitado.

Thomas Ahle
fuente