[727374]

I went down the Bloom Filter rabbit hole for a project a while back and then wondered if I could actually fit the entire set space in memory. The set was IDs up to 2^32, so basically a giant bit array. I believe the IPV4 universe of this article is actually the same size as in my project. I coded up my project using Java bit arrays and got things working decently well, using a big heap. Then I found out there are a bunch of compressed bit array libraries such as EWAH and Roaring Bitmap. When I substituted Roaring for the stock Java Bitset implementation, I saw space and computation improve by many orders of magnitude. Roaring uses a bunch of tricks to achieve this, but it mostly comes down to encoding large runs of 1s or 0s. Obviously, not as tiny as bloom filters, but still pretty small for most modern machines if you have a sparse set. https://www.roaringbitmap.org/

[deepsun]

And it's not probabilistic, it gives strict answer whether an element is in the set or not.

[aforwardslash]

+1 to roaring bitmap. I've actually implemented a PoC in golang with roaring bitmap to keep IPv4 maps (unfortunately its closed-source, at least for now) and it seems to be quite efficient, both performance-wise and memory-wise, at least in the "millions of entries" range.