4 ms·
You don't need to keep the lists, just keep a Bloom filter of sufficient size to keep false positives low.
by sparkie 3y ago
You don't need to keep the lists, just keep a Bloom filter of sufficient size to keep false positives low.
- CodesInChaos 3y agoYou can at best save log2(n)-1.4 bits per entry using smarter encoding compared to a naive list. That's perhaps a factor of 2-3x, depending on list size and acceptable false positive rate. For example if you have a list of a billion entries and accept a one in a million false positive rate, the naive list needs 30+20=50 bits, while an ideal encoding will need 21.4 bits, a 57% reduction. So I don't think bloom filters have a significant impact on the manageability of those lists. Though I doubt the storage size will be the main concern, compared to the effort of adding entries to that list.