Comment by Freaky | Hacker News Reader

Comment by Freaky | Hacker News Reader

Parent Full thread

> 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 [2]: https://github.com/Freaky/gcstool [3]: https://github.com/Freaky/ruby-gcs [4]: http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-s...

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?

> 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

Reply on news.ycombinator.com