Is there any probabilistic data structure that gives false negatives but not false positives?

Question

I need a space efficient probabilistic data structure to store values that I have already computed. For me computation is cheap but space is not - so if this data structure returns a false negative, I am okay with redoing some work every once in a while but false positives are unacceptable. So what I am looking for is sort of the opposite of a Bloom filter.

Answer 1

For false negative you can use lossy hash table or a LRUCache. It is a data structure with fast O(1) look-up that will only give false negatives. if you ask if "Have I run test X", it will tell you either "Yes, you definitely have", or "I can't remember".

Pseudocode:

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.

Similarly Bloom filter for false positive