Mar 10, 2025

So it's been nagging me that this should be doable with positive (no delete) accumulation during download, across download threads, in a lock-free manner, without having to search the point table at all. So I worked through some statistical accumulation options, and had Grok do some sizing. I also pulled out the actual conflict rates in the point table, as this is critical for the estimation. I looked at Bloom and Cuckoo filtering, and settled on Bloom because it's far more space efficient because it doesn't support deletion - which we don't need. Either can be performed concurrently in a lock free manner, though Bloom is a little more complex to do so. Cuckoo would be basically using our hashmap header template, and its memory fencing. Bloom requires striping the filter by thread (basically independent filters, sharding the space). Bloom also requires more computation, but that's pretty trivial.