4 ms·

> a bloom filter for 502M entries and a false positive rate of 0.1% ends up as a 800MiB large filter With that sort of FP rate it's not really much use beyond

by Freaky 8y ago

> a bloom filter for 502M entries and a false positive rate of 0.1% ends up as a 800MiB large filter With that sort of FP rate it's not really much use beyond filtering API calls. I'd suggest 2GB[1] as a more sensible minimum. A compressed filter can get this down somewhat. > Binary-searching the whole dump is surely faster. Not really. log2(500M) is ~29, k for a suitably sized bloom filter's only 23. Interpolation search can get you a result in more like 10 seeks, but a bucketed bloom filter can get your lookup down to a single read. Having spent a fair bit of time faffing about with this stuff I ended up settling[2][3] on Golomb compressed sets[4], which can get the full list with a 1-in-10 million FP rate into 1.5GB. [1]: https://hur.st/bloomfilter/?n=500M&p=1.0E-7 https://hur.st/bloomfilter/?n=500M&p=1.0E-7 [2]: https://github.com/Freaky/gcstool https://github.com/Freaky/gcstool [3]: https://github.com/Freaky/ruby-gcs https://github.com/Freaky/ruby-gcs [4]: http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-smaller-than-bloom-filters http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-s...

minus7 8y ago
Oh right, I was wrongly thinking you'd have to memcmp the whole size of the filter. It's simply too warm today for thinking. Did you look into Cuckoo filters as well?
- Freaky 8y ago
  > Oh right, I was wrongly thinking you'd have to memcmp the whole size of the filter. Yeah, it's just k single-bit lookups - ideally you do something to get them into clusters, like dividing the database into sub-filters, so you're doing random lookups into, say, a 32KB chunk instead of a whole 2GB filter. > Did you look into Cuckoo filters as well? Cuckoo filters look like an interesting alternative and looking at them more closely is on the to-do. I don't think they'd have any significant space savings, though - they're similarly about 75% the size of the equivalent bloom filter. Maybe they'd be faster for lookups? I'd also be interested in playing with matrix filters[1], which supposedly get close to the theoretical limits for these sorts of structures. Implementing them seems rather more involved, sadly - particularly given the only reference I can find is a fairly inscrutable CS paper. Show us the code damnit. [1]: https://arxiv.org/abs/0804.1845 https://arxiv.org/abs/0804.1845

by Freaky 8y ago

minus7 8y ago

Oh right, I was wrongly thinking you'd have to memcmp the whole size of the filter. It's simply too warm today for thinking. Did you look into Cuckoo filters as well?

Freaky 8y ago
> Oh right, I was wrongly thinking you'd have to memcmp the whole size of the filter. Yeah, it's just k single-bit lookups - ideally you do something to get them into clusters, like dividing the database into sub-filters, so you're doing random lookups into, say, a 32KB chunk instead of a whole 2GB filter. > Did you look into Cuckoo filters as well? Cuckoo filters look like an interesting alternative and looking at them more closely is on the to-do. I don't think they'd have any significant space savings, though - they're similarly about 75% the size of the equivalent bloom filter. Maybe they'd be faster for lookups? I'd also be interested in playing with matrix filters[1], which supposedly get close to the theoretical limits for these sorts of structures. Implementing them seems rather more involved, sadly - particularly given the only reference I can find is a fairly inscrutable CS paper. Show us the code damnit. [1]: https://arxiv.org/abs/0804.1845 https://arxiv.org/abs/0804.1845