Is this worth reading? The text is LLM slop.
Two Bits Are Better Than One: making bloom filters 2x more accurate
21–30 of 36 posts
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#22Is this worth reading? The text is LLM slop.
> The win? Massive.
But there are benchmark numbers at least, so maybe they only used it for the prose
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#23Hmm, Bloom filters seem important. I'm wondering why my CS education never even touched on them and it's tbh triggering my imposter syndrome.
Distributed systems and probabilistic data structures really should be in every undergrad CS curriculum even if just in passing for the second
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#24This 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…
Yeah, I agree with this. I think there are open addressing hash tables like Swiss Table that do something similar. IIRC, they have buckets with a portion at the beginning with lossy “fingerprints” of items, which kind of serve a similar purpose as a bloom filter.
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#25This 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…
Yeah I kind of think authors didn't conduct a thorough-enough literature review here. There are well-known relations between number of hash functions you use and the FPR, cache-blocking and register-blocking are classic techniques (Cache-, Hash-, and Space-Efficient Bloom Filters by Putze et. al), and there are even ways of generating patterns from only a single hash function that works well (shamelessly shilling my…
Very interesting blog post. I’d never seen that method for quickly computing the patterns. I thought I had done a lot of research on bloom filters, too!
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#26Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#27This 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…
Problem is bloom isn’t close to the theoretical space complexity of the idea it implements and if you add 15% then it starts becoming attractive to switch to one that gets a tighter bound on the space complexity.
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#28This 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…
Bloom filters are useful for sharding so it stands to reason that a hash table implemented with shards would benefit.
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#29Hmm, Bloom filters seem important. I'm wondering why my CS education never even touched on them and it's tbh triggering my imposter syndrome.
I made it until Google posted an article about their use of Bloom Filters back around -2000 before I even heard of them, which is at least 25 years after they were invented. Anger was my emotion, not impostor syndrome. I went to a top ten school and none of my profs thought to mention it. Had to learn AVL trees twice though. Which I’ve used fuck-all.
Re: Two Bits Are Better Than One: making bloom filters 2x more accurate
#30Hmm, Bloom filters seem important. I'm wondering why my CS education never even touched on them and it's tbh triggering my imposter syndrome.
Distributed systems and probabilistic data structures really should be in every undergrad CS curriculum even if just in passing for the second
That curriculums didn’t have distributed computing classes when I was in school (mine did, but few took it) made some sense. That modern coursework omits it is unconscionable.