Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Two Bits Are Better Than One: making bloom filters 2x more accurate

floedb.ai

Post reply on HN
Print view View original

31–36 of 36 posts

Re: Two Bits Are Better Than One: making bloom filters 2x more accurate

#31

Post by SolarNet »

vlmutolo wrote: post #4

This article is a little confusing. I think this is a roundabout way to invent the blocked bloom filter with k=2 bits inserted per element. It seems like the authors wanted to use a single hash for performance (?). Maybe they correctly determined that naive Bloom filters have poor cache locality and reinvented block bloom filters from there. Overall, I think block bloom filters should be the default most people reach…

Cause it was written by AI.the entire mid section is classic AI slop writing. Repeating the same points and numbers over and over, repackaging the same idea with "key takeaway" and shit. The voice of the author is heavily AI coded there.

Re: Two Bits Are Better Than One: making bloom filters 2x more accurate

#32

Post by vanderZwan »

Sesse__ wrote: post #18
vlmutolo wrote: post #4

This article is a little confusing. I think this is a roundabout way to invent the blocked bloom filter with k=2 bits inserted per element. It seems like the authors wanted to use a single hash for performance (?). Maybe they correctly determined that naive Bloom filters have poor cache locality and reinvented block bloom filters from there. Overall, I think block bloom filters should be the default most people reach…

> Overall, I think block bloom filters should be the default most people reach for. I think this depends on how big your filters are. Most people think of Bloom filters as having to have hundreds of thousands of elements, but I frequently find them useful all the way down to 32 bits (!). (E.g., there are papers showing chained hash tables where each bucket has a co-sited tiny Bloom filter to check if it's worth probi…

Are you talking about Cuckoo++ tables, perhaps? If not can you point me to the hash table you had in mind? Always fun to learn of a new approach.

https://github.com/technicolor-research/cuckoopp

Re: Two Bits Are Better Than One: making bloom filters 2x more accurate

#33

Post by Sesse__ »

vanderZwan wrote: post #32
Sesse__ wrote: post #18

Earlier quoted context omitted.

> Overall, I think block bloom filters should be the default most people reach for. I think this depends on how big your filters are. Most people think of Bloom filters as having to have hundreds of thousands of elements, but I frequently find them useful all the way down to 32 bits (!). (E.g., there are papers showing chained hash tables where each bucket has a co-sited tiny Bloom filter to check if it's worth probi…

Are you talking about Cuckoo++ tables, perhaps? If not can you point me to the hash table you had in mind? Always fun to learn of a new approach. https://github.com/technicolor-research/cuckoopp

IIRC, it's this paper: https://db.in.tum.de/~birler/papers/hashtable.pdf

I never implemented their hash table, but it opened my eyes to the technique of a tiny Bloom filter, which I've used now a couple of times to fairly good (if small) effect. :-)

Re: Two Bits Are Better Than One: making bloom filters 2x more accurate

#34

Post by vanderZwan »

Sesse__ wrote: post #33
vanderZwan wrote: post #32

Earlier quoted context omitted.

Are you talking about Cuckoo++ tables, perhaps? If not can you point me to the hash table you had in mind? Always fun to learn of a new approach. https://github.com/technicolor-research/cuckoopp

IIRC, it's this paper: https://db.in.tum.de/~birler/papers/hashtable.pdf I never implemented their hash table, but it opened my eyes to the technique of a tiny Bloom filter, which I've used now a couple of times to fairly good (if small) effect. :-)

Thanks! This'll be a fun read :)

Re: Two Bits Are Better Than One: making bloom filters 2x more accurate

#35

Post by holoskii »

vlmutolo wrote: post #4

This article is a little confusing. I think this is a roundabout way to invent the blocked bloom filter with k=2 bits inserted per element. It seems like the authors wanted to use a single hash for performance (?). Maybe they correctly determined that naive Bloom filters have poor cache locality and reinvented block bloom filters from there. Overall, I think block bloom filters should be the default most people reach…

Post author here. Yes, you are correct. I was doing this code change 3 years ago when I was a junior dev, I was not familiar with a blocked bloom filters at that time. Looking back, it’s cool to see that I accidentally reinvented a basic blocked bloom.

I was also limited by the constraint of legacy code. This project was not a complete rewrite, but just an idea: "can we use more information from that 32-bit hash that we recieve in without regressing any perf". We didn't have a time for a deep research or a rewrite, so I just wanted to show the result of this small exercise on how we can make things run better without rewriting the world.

Re: Two Bits Are Better Than One: making bloom filters 2x more accurate

#36

Post by holoskii »

londons_explore wrote: post #11

What are they running this code on? I doubt their hardware is any faster shuffling bits in a uint32 than a uint64, and using uint64 should have a decent benefit to the false positive rate...

It was just an oversight. Thinking about it now, u64 could have been better:

1. intra element collison goes down: 1/32 = 3.1% vs 1/64 = 1.6% -> 1.5% difference. Intra element collison doesn't mean guaranteed a FP though! 2. 64 bucket would have less variance - filter behavior would be more predictable

But there is a downside: When switching from 32 to 64 bit word we also reduce number of array elements 2 times, doubling the contention. We are populating the filter from up to 128 threads during join phase. When the build side isn't significantly smaller than the probe side, that contention can overweight the FP improvement.

Post reply on HN