3 ms·
Was thinking a 'reverse bloom filter' could be cool to possibly avoid the RocksDB for situations like this- turns out it already exists: https://github.com/jmho
by siliconc0w 9y ago
Was thinking a 'reverse bloom filter' could be cool to possibly avoid the RocksDB for situations like this- turns out it already exists:
https://github.com/jmhodges/opposite_of_a_bloom_filter https://github.com/jmhodges/opposite_of_a_bloom_filter
I love it when that happens.
- openasocket 9y agoIt should be noted it's impossible to have a 'reverse bloom filter' with the same properties as a regular bloom filter. That is, a constant predefined size gives you a particular false negative rate. The thing you linked to is really just a cache. It has to store an entire entry (not just set some bits based on the hash) and doesn't have a predictable false negative rate based on its size. For more info: https://cstheory.stackexchange.com/questions/6596/a-probabilistic-set-with-no-false-positives https://cstheory.stackexchange.com/questions/6596/a-probabil...