5 ms·

This seems like an alright solution, but I think an LRU or LFU cache would perform better (they wouldn't have pathological cases like two colliding events that

This seems like an alright solution, but I think an LRU or LFU cache would perform better (they wouldn't have pathological cases like two colliding events that frequently alternate), and you probably wouldn't have to implement it yourself. I also think it's a bit much to call this "the opposite of a bloom filter". A bloom filter has a lot of properties that don't come through in the algorithm proposed. For one thing, the space required is O(MN) (size of an element * size of the filter) instead of a bloom filter's O(N). For another, bloom filters give the same results regardless of what order previous elements were added in. It seems to me that if you're looking for "the opposite of a bloom filter", you're probably wanting those properties.

sweezyjeezy 11y ago
The space requirement is surely impossible to fulfil generically. As soon as you do any sort of compression you make it possible for two elements to map to the same thing. Unless you know that M << N, in which case you can just save exactly one element, and just replace it every time you see a new one!
- deleted 11y ago
  [deleted]
- mistercow 11y ago
  That's basically true. Technically you can meet these requirements by exploiting the false negatives loophole, but if the data structure can ever report that it contains a size M element, it will need O(M) space.
forgotpwtomain 11y ago
It depends how you implement your hash-table, for example I've done something similar using cuckoo hashing: https://github.com/pik/time-rotated-cache-filter https://github.com/pik/time-rotated-cache-filter > It seems to me that if you're looking for "the opposite of a bloom filter", you're probably wanting those properties. You can't really get a theoretical opposite of a bloom-filter unless you store the entries verbatim, since any hash/compression introduces the chance of collisions meaning you can only provide probabilistic guarantees where as a bloom-filter gives a strong guarantee.
vmarsy 11y ago
>they wouldn't have pathological cases like two colliding events that frequently alternate To avoid this particular case you could always add a "victim cache" : In that case a similar but smaller, second hash table which uses the same hashing function and follow the same protocol as a regular victim cache. See: http://www.ecs.umass.edu/ece/koren/architecture/VCache/home.html http://www.ecs.umass.edu/ece/koren/architecture/VCache/home....

sweezyjeezy 11y ago

The space requirement is surely impossible to fulfil generically. As soon as you do any sort of compression you make it possible for two elements to map to the same thing. Unless you know that M << N, in which case you can just save exactly one element, and just replace it every time you see a new one!

deleted 11y ago
[deleted]
mistercow 11y ago
That's basically true. Technically you can meet these requirements by exploiting the false negatives loophole, but if the data structure can ever report that it contains a size M element, it will need O(M) space.

forgotpwtomain 11y ago

It depends how you implement your hash-table, for example I've done something similar using cuckoo hashing: https://github.com/pik/time-rotated-cache-filter https://github.com/pik/time-rotated-cache-filter > It seems to me that if you're looking for "the opposite of a bloom filter", you're probably wanting those properties. You can't really get a theoretical opposite of a bloom-filter unless you store the entries verbatim, since any hash/compression introduces the chance of collisions meaning you can only provide probabilistic guarantees where as a bloom-filter gives a strong guarantee.

vmarsy 11y ago

>they wouldn't have pathological cases like two colliding events that frequently alternate To avoid this particular case you could always add a "victim cache" : In that case a similar but smaller, second hash table which uses the same hashing function and follow the same protocol as a regular victim cache. See: http://www.ecs.umass.edu/ece/koren/architecture/VCache/home.html http://www.ecs.umass.edu/ece/koren/architecture/VCache/home....