Alt text:
Sometimes, you can tell Bloom filters are the wrong tool for the job, but when they’re the right one you can never be sure.
Alt text:
Sometimes, you can tell Bloom filters are the wrong tool for the job, but when they’re the right one you can never be sure.
There’s a recent algorithm using somewhat similar ideas for approximate counting of unique objects in a stream with constant memory:
https://www.quantamagazine.org/computer-scientists-invent-an-efficient-new-way-to-count-20240516/
I think I like hash-based probabilistic counting better, but this is interesting