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

Question

I need a spatial effective probabilistic data structure to store the values ​​that I have already calculated. For me, computing is cheap, but space is not - therefore, if this data structure returns a false negative, I am fine with repeating some work every once in a while, but false positives are unacceptable. So I'm looking for something like the opposite of a Bloom filter .

Answer 1

For a fake negative value, you can use a lossy hash table or LRUCache. This is a data structure with a quick search of O (1), which will give only false negatives. if you ask, “If I run test X,” he will tell you, “Yes, you definitely have” or “I don’t remember.”

pseudo code:

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, a Bloom filter for false positives