data structures - ¿Frente al filtro Bloom?

data-structures bloom-filter

Question

Estoy tratando de optimizar un software que básicamente ejecuta millones de pruebas. Estas pruebas se generan de tal manera que puede haber algunas repeticiones. Por supuesto, no quiero perder tiempo ejecutando pruebas que ya realicé si puedo evitarlo de manera eficiente.

Entonces, estoy pensando en usar un filtro Bloom para almacenar las pruebas que ya se han ejecutado. Sin embargo, el filtro Bloom se equivoca en el lado inseguro para mí. Da falsos positivos. Es decir, puede informar que realicé una prueba que no hice. Aunque esto podría ser aceptable en el escenario en el que estoy trabajando, me preguntaba si existe un equivalente a un filtro Bloom, pero se equivoca en el lado opuesto, es decir, solo se dan falsos negativos.

He hojeado la literatura sin suerte.

Answer 1

1. Use un juego de bits, como se mencionó anteriormente. Si sabes el no. de las pruebas que va a ejecutar de antemano, siempre obtendrá los resultados correctos (presente, no presente) de la estructura de datos.
2. ¿Sabes qué claves serás hashing? Si es así, debe ejecutar un experimento para ver la distribución de las claves en BloomFilter para que pueda ajustarlo y reproducir falsos positivos, o lo que sea.
3. También es posible que desee comprobar HyperLogLog.

Answer 2

¿Es posible almacenar las pruebas que no ejecutó? Esto debería invertir el comportamiento del filtro.

Answer 3

¿Qué tal un LRUCache?

Answer 4

Creo que estás dejando de lado parte de la solución; para evitar falsos positivos por completo, aún tendrá que rastrear los que se han ejecutado, y esencialmente utilizar el filtro de floración como un atajo para determinar que la prueba definitivamente no se ha ejecutado.

Dicho esto, dado que conoce el número de pruebas por adelantado, puede ajustar el tamaño del filtro de manera que proporcione una tasa de error aceptable utilizando algunas fórmulas bien conocidas; para una probabilidad del 1% de devolver un falso positivo necesitas ~ 9.5 bits / entrada, por lo que para un millón de entradas son suficientes 1.2 megabytes. Si reduce la tasa de error aceptable al 0.1%, esto solo aumenta a 1.8 MB.

El artículo de Wikipedia Bloom Filters ofrece un excelente análisis y una descripción interesante de las matemáticas involucradas.

Answer 5

La estructura de datos exacta que realiza esta tarea es una memoria caché de mapeo directo , y se usa comúnmente en las CPU.

function set_member(set, item)
    set[hash(item) % set.length] = item

function is_member(set, item)
    return set[hash(item) % set.length] == item

Answer 6

La estructura de datos que espera no existe. Debido a que dicha estructura de datos debe ser un mapeo de varios a uno, o por ejemplo, un conjunto de estados limitados. Debe haber al menos dos entradas diferentes asignadas al mismo estado interno. Por lo tanto, no puede decir si ambos (o más) de ellos están en el conjunto, solo sabiendo que al menos uno de dichos datos existe.

EDITAR Esta afirmación es verdadera solo cuando está buscando una estructura de datos eficiente en la memoria. Si la memoria es ilimitada, siempre puede obtener una estructura de datos para obtener resultados 100% precisos, almacenando cada elemento miembro.

Answer 7

Lo siento, no soy de mucha ayuda, no creo que sea posible. Si no se puede ordenar la ejecución de la prueba, quizás use un formato empaquetado (¡8 pruebas por byte!) O una buena biblioteca de matriz dispersa para almacenar los resultados en la memoria.

Answer 8

No, y si lo piensas, no sería muy útil. En su caso, no podría estar seguro de que su prueba se detendría alguna vez, porque si siempre hay "falsos negativos" siempre habrá pruebas que deben ejecutarse ...

Yo diría que solo tienes que usar un hash.

Answer 9

Sí, una tabla hash con pérdidas o una LRUCache es una estructura de datos con una búsqueda O (1) rápida que solo arrojará resultados negativos falsos. Si pregunta "¿He ejecutado la prueba X?", Le dirá "Sí, definitivamente tener ", o" No puedo recordar ".

Perdona el pseudocódigo extremadamente crudo:

setup_test_table():
    create test_table( some large number of entries )
    clear each entry( test_table, NEVER )
    return test_table

has_test_been_run_before( new_test_details, test_table ):
    index = hash( test_details , test_table.length )
    old_details = test_table[index].detail
    // unconditionally overwrite old details with new details, LRU fashion.
    // perhaps some other collision resolution technique might be better.
    test_table[index].details = new_test_details
    if ( old_details === test_details ) return YES
    else if ( old_details === NEVER ) return NEVER
    else return PERHAPS    

main()
    test_table = setup_test_table();
    loop
        test_details = generate_random_test()
        status = has_test_been_run_before( test_details, test_table )
        case status of
           YES: do nothing;
           NEVER: run test (test_details);
           PERHAPS: if( rand()&1 ) run test (test_details);
    next loop
end.