Comment by Const-me | Hacker News Reader

Comment by Const-me | Hacker News Reader

There’s a useful but non-obvious property of these filters.

If you have two Bloom filters which use same set of possible keys and same filter setup, you can compute intersection of their represented sets with a bitwise AND operation over the bitsets in these filters.

If you store bitsets aligned and padded by SIMD vector size (for example, an array of __m128i in C++ as opposed to the array of uint64 values in the golang example), computing such intersection is very efficient on modern computers.

I once used that technique to filter 3D objects from a large set using the intersection of 3 range queries, one per coordinate. Compute two Bloom filters filled with the objects returned by X and Y queries, intersect the filters, then iterate over the objects returned by the remaining Z query testing against the intersected Bloom filter. Due to probabilistic nature of the Bloom filter you still need to test for X and Y queries for the objects tested positive by the filter, however with proper setup the filter should reject vast majority of them.

That's pretty clever. In my 3D experiments I always struggled with minimizing the number of objects in the world I had to consider for rendering on each frame based on the view/fog(range). This seems like it would help with that.

Have you tried using Quad Tree?

Yes! There was a great Graphics Gems article on implementing quad trees. The things that change are the sheer number of things you might have in your environment.

So, in the end did quad tree help you solve the problem, or you needed something else?

End the end I gave up :-) The problem I was trying to solve was a physics based deformable environment. Something like minecraft but without the blockyness. Basically allowing one to dig as deep as one wanted into the planet, build as high as one wanted, and re-arrange as much as one wanted all with physics rules combined with some matter composition rules that would give one an 'authentic' experience. It was a stretch in the 90's and I think I stopped poking at it around 2005 :-). But part of the problem was when you broke things you got multiple sub-objects. Potentially down to the level of "sand" (which in my world was a .001cc chunk.)

From what I understand bloom filters have a hash per item but when i invented (hah) them I used a bit array for each property where each bit describes an item at the same offset. When searching for some properties one can do an AND on those entire arrays and eliminate candidates really fast.

Reply on news.ycombinator.com