3 ms·

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

• 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