¿Un conjunto probabilístico sin falsos positivos?

35

Por lo tanto, los filtros Bloom son bastante geniales: son conjuntos que admiten la verificación de membresía sin falsos negativos, pero con una pequeña posibilidad de un falso positivo. Recientemente, sin embargo, he estado buscando un "filtro Bloom" que garantice lo contrario: sin falsos positivos, pero potencialmente falsos negativos.

Mi motivación es simple: dada una gran cantidad de elementos para procesar (con duplicados), nos gustaría evitar el procesamiento de elementos que hemos visto antes. No hace daño procesar un duplicado, es solo una pérdida de tiempo. Sin embargo, si descuidamos procesar un elemento, sería catastrófico. Con un "filtro de Bloom inverso", se podrían almacenar los elementos vistos con poco espacio encima y evitar el procesamiento de duplicados con alta probabilidad al probar la membresía en el conjunto.

Sin embargo, parece que no puedo encontrar nada por el estilo. Lo más cercano que he encontrado son los " filtros Bloom retocados ", que permiten intercambiar falsos positivos seleccionados por una tasa de falsos negativos más alta. Sin embargo, no sé qué tan bien funciona su estructura de datos cuando uno quiere eliminar todos los falsos positivos.

¿Alguien ha visto algo como esto? :)

Christopher Monsanto
fuente
3
El complemento del conjunto que me interesa es infinito. ¿Cómo lo guardaría?
Christopher Monsanto
11
Veo el problema (los discos modernos aún no son lo suficientemente grandes).
Dave Clarke
8
Si tuviera una estructura de datos de este tipo, podría usarla para "hacer trampa" al usarla junto con un filtro de floración regular y almacenar la membresía exacta del conjunto.
Mark Reitblatt
1
@ MarkReitblatt, tanto los filtros Bloom como los cachés son probabilísticos, y cualquier combinación de los mismos será probabilístico, es decir, no podrá lograr una prueba de membresía de conjunto exacta. :)
awdz9nld

Respuestas:

25

Una respuesta es usar una tabla hash grande y cuando se llene, comenzar a reemplazar elementos en lugar de encontrar espacios vacíos (inexistentes) en otro lugar para ellos. No obtienes la buena tasa fija de respuestas falsas que haces con los filtros Bloom, pero es mejor que nada. Creo que esto es estándar, por ejemplo, en el software de ajedrez para realizar un seguimiento de las posiciones que ya se han buscado.

David Eppstein
fuente
Gracias por la respuesta. Sí, esa es la solución obvia; si también es la solución estándar , parece que no tengo suerte. Oh bien.
Christopher Monsanto
2
Esto se llama caché de asignación directa y se usa comúnmente en las CPU. (Cualquier conjunto de memoria caché o hash con pérdida se ajusta a los requisitos en diversos grados). La tasa de error es una función de la distribución de la función hash (avalancha) y el número de ranuras disponibles en el caché / conjunto: ajústelo en consecuencia. :)
awdz9nld
También tenga en cuenta que solo las claves textuales se pueden almacenar sin introducir falsos positivos (por ejemplo, almacenar una clave hash)
awdz9nld
20

La respuesta a esta pregunta es no". Para ver por qué, podemos pensar en un caso muy extremo y cómo funcionaría un filtro de floración regular frente a un filtro de floración teórico "Bizzaro World", que podemos llamar un "filtro sombrío".

Lo bueno de un filtro de floración es que puede hacer pruebas unilaterales para la pertenencia de elementos (con falsos positivos) utilizando una estructura de datos que tiene un tamaño fijo con respecto a la probabilidad de error y la cantidad de elementos almacenados. El tamaño de los artículos en sí no importa en absoluto. Por ejemplo, si tuviéramos un filtro de floración configurado para almacenar hasta 1,000 artículos con menos del 3% de error, entonces podríamos almacenar 1,000 versiones ligeramente diferentes de todo el corpus de Wikipedia, con una letra cambiada en cada una, y aún así obtener las métricas que queremos, y la estructura de datos sería muy pequeña (menos de un kilobyte). Por supuesto, calcular esos hash será un desafío, pero el principio aún se mantiene.

¡Ahora, considere almacenar esas mismas cadenas masivas en un filtro sombrío! Solo podemos tener falsos negativos ahora. Entonces, si decimos "sí, esa versión de todo el corpus de Wikipedia está en este conjunto", entonces tenemos que tener toda la razón al respecto. Eso significa que el hash no nos ayudará, ya que siempre habrá alguna otra cadena que tenga el mismo valor. La única forma de decir "sí" y asegurarse es almacenar toda la cadena o algunos datos equivalentes de la misma longitud. Siempre no podíamos almacenarlo y decir "no", pero eventualmente la tasa de error nos alcanzará. Lo mejor que podríamos hacer es la compresión, reduciendo el tamaño de la estructura al producto de la entropía de los datos almacenados y la precisión que deseamos.

Entonces, desafortunadamente el filtro sombrío no existe. El almacenamiento en caché es la única solución, pero en realidad no es lo opuesto a un filtro de floración, ya que su tamaño será proporcional al producto de la cantidad de información que se almacena y la tasa de precisión deseada del filtro. Por supuesto, en muchos escenarios del mundo real, los datos grandes pueden representarse mediante una ID, por lo que el almacenamiento en caché puede ser bastante aceptable. Pero es fundamentalmente diferente al poderoso filtro de floración.

pents90
fuente
checkout somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter - qué tiene de malo esta implementación /
Yehosef
@Yehosef está bien y puede funcionar para sus necesidades, pero notará que el autor habla de que hay "algunas ID que identifican completamente el evento". Entonces, lo que se implementa es efectivamente almacenar todo el objeto. Entonces, es una variante de un caché. Un "opuesto real a un filtro de floración", si existiera, no necesitaría almacenar objetos completos.
pents90
Mencionó algunos identificadores que identifican el evento, no todo el objeto. Solo necesito mantener el "caché" en session_id, no todo el registro de interacción. Pero escuché que no es el mismo tipo de enfoque que el bloom o un hiperloglog.
Yehosef
En su "prueba", usted asume que hay un número ilimitado de entradas posibles. Sin embargo, hay casos en los que el conjunto de posibles entradas se conoce de antemano. Por ejemplo, para la recolección de basura de una página de memoria: usted sabe qué entradas contiene. Ahora crea un "filtro sombrío" que asigna cada entrada posible a un índice 0..n. Ahora, cuando se elimina una entrada, establezca el bit en ese índice. Cuando se establecen todos los bits, puede recolectar basura de la página. El "filtro sombrío" es un MPHF. Para permitir falsos negativos, cambie el MPHF de modo que algunas entradas se asignen a n + 1.
Thomas Mueller
@ThomasMueller Correcto, estoy asumiendo el peor de los casos / caso adversario, que es el punto de vista estándar de la teoría CS. Es cierto que si solo tiene un conjunto fijo de N entradas posibles, entonces hay muchas soluciones sencillas, con solo espacio de registro N requerido para cada elemento. Sin embargo, el filtro de floración no tiene tales limitaciones.
pents90
13

Solo quieres un caché , pero lo estás pensando de una manera extraña.

Craig Gidney
fuente
1
... ¿cuidado para elaborar? Por supuesto, un caché funcionaría, pero eso no es ideal, de ahí una pregunta sobre el estado del arte en estructuras de datos probabilísticas. Para ser más específicos: las técnicas de almacenamiento en caché que conozco requieren mucho almacenamiento. Cuantos más niveles de caché, más almacenamiento se usa. Uno podría colocar un límite en los elementos almacenados en la memoria caché, hacer trucos con patrones de uso, etc., pero eso aún no se acerca a la eficiencia del espacio a la relación de respuesta falsa que proporciona un filtro Bloom.
Christopher Monsanto
1
(continuación) Dicho esto, podría olvidarme de una técnica de almacenamiento en caché obvia que resuelve todos mis problemas. En ese caso, ¿podría hacer explícita esa técnica en lugar de darme un enlace a una categoría general en Wikipedia?
Christopher Monsanto
2

DESCARGO DE RESPONSABILIDAD: No soy un experto en cachés, por lo que esta podría ser una idea ingenua, y también puede ser una idea conocida de la que nunca antes había oído hablar. Así que discúlpeme si no puedo citar su referencia (si existe); e infórmeme si hay una referencia para editar la publicación y agregarla. (Sospecho que podría tener una referencia porque es muy intuitivo).

cc

M. Alaggan
fuente
0

He usado árboles AVL (y a veces rojo-negro) con elementos parciales para actuar como un filtro sin falsos negativos. Use solo los primeros X bytes del elemento al insertar o consultar el árbol. Debido a que la estructura de datos no es de forma probabilística, no existe el riesgo de una falsa colisión por bit positivo. Y a diferencia del almacenamiento en caché de todo el elemento, este enfoque le brinda un espacio máximo calculable. Puede ajustar la tasa de falsos positivos considerando diferentes longitudes de prefijo / profundidades de árbol en comparación con el costo de los falsos positivos y el espacio.

JRideout
fuente
También he querido probar los intentos con datos de cadena, pero mis datos tienden a ser estructuras binarias empaquetadas.
JRideout
0

Creo que se puede probar un límite inferior que indica que la estructura de datos anterior no puede existir. Básicamente, si la estructura de datos usa m bits, entonces un vector de bits fijo (representación de una entrada) puede corresponder como máximo a (((un) + n eps) \ elegir (un)) conjuntos mediante un argumento de conteo. Dado que 2 ^ m veces este número debe ser al menos (u \ choose n) (todos los conjuntos deben estar representados), obtenemos un límite inferior que está básicamente muy cerca de almacenar el conjunto S con precisión.

Mayank
fuente