What are Bloom filters? (2015)
medium.com
What are Bloom filters? (2015)
1–10 of 71 posts
Re: What are Bloom filters? (2015)
#2Bloom filters are beautiful and highly underutilized.
I used a Bloom filter in an interview and they looked at me like it was some form of arcane sorcery.
Isn't this standard in algorithms and data structures courses? Does anyone know if it has been removed from the curriculum?
Re: What are Bloom filters? (2015)
#3Bloom filters are beautiful and highly underutilized. I used a Bloom filter in an interview and they looked at me like it was some form of arcane sorcery. Isn't this standard in algorithms and data structures courses? Does anyone know if it has been removed from the curriculum?
> Does anyone know if it has been removed from the curriculum?
I don't think there is such a thing as a single curriculum taught by all colleges that it could have been removed from.
Re: What are Bloom filters? (2015)
#4Bloom filters are beautiful and highly underutilized. I used a Bloom filter in an interview and they looked at me like it was some form of arcane sorcery. Isn't this standard in algorithms and data structures courses? Does anyone know if it has been removed from the curriculum?
It is not standard, and was never added to most uni programs in the first place.
Re: What are Bloom filters? (2015)
#5Fyi... the previous discussion about venison glazed in honey (or was it bloom filters? I can't remember for sure):
(July 2015) https://news.ycombinator.com/item?id=9918365
Re: What are Bloom filters? (2015)
#6Bloom filters are beautiful and highly underutilized. I used a Bloom filter in an interview and they looked at me like it was some form of arcane sorcery. Isn't this standard in algorithms and data structures courses? Does anyone know if it has been removed from the curriculum?
> Does anyone know if it has been removed from the curriculum? I don't think there is such a thing as a single curriculum taught by all colleges that it could have been removed from.
I'm speaking more of generalized educational practice than standardized curricula.
Re: What are Bloom filters? (2015)
#7Brilliant! I never anticipated Bloom filters would be so simple. What comes to my mind is that for "forgetful" Bloom filters, one could remove a hash from the table, also erasing all equivalent entries from the memory. Is this a useful trade-off in practice?
Re: What are Bloom filters? (2015)
#8Bloom filters are beautiful and highly underutilized. I used a Bloom filter in an interview and they looked at me like it was some form of arcane sorcery. Isn't this standard in algorithms and data structures courses? Does anyone know if it has been removed from the curriculum?
Bloom filters have a lot of problems for critical processes in practice. They are best used when being wrong is a non issue or as a type of cache, but preforming a hash is generally really slow. Also, the way virtual memory works looking up an answer often makes storing the new value much faster.
So, while cool they have generally been replaced by far more useful and less complex topics.
One example is if your looking for duplicates among huge data sets. You farm out your Filter to 1,000 machines merge them, then re run to get a list of possible collisions. Then compare that list. But, well merge sort can do the same thing a little slower, it's a rare problem, and the pathological case for Bloom filters is really bad. So, even if you know about Bloom filters you may go with the simpler idea and be done sooner.
PS: In that example hash speed might mean sorting is actually faster.
Re: What are Bloom filters? (2015)
#9Earlier quoted context omitted.
> Does anyone know if it has been removed from the curriculum? I don't think there is such a thing as a single curriculum taught by all colleges that it could have been removed from.
I'm speaking more of generalized educational practice than standardized curricula.
I do believe you specifically asked:
Isn't this standard in algorithms and data structures courses?
And the answer was 'no'.
It's okay to be publicly wrong. You wanted to learn something and now you know. But acting like you didn't ask it because you're feeling self-conscious just makes the whole thing awkward for everybody.
Re: What are Bloom filters? (2015)
#10Bloom filters are beautiful and highly underutilized. I used a Bloom filter in an interview and they looked at me like it was some form of arcane sorcery. Isn't this standard in algorithms and data structures courses? Does anyone know if it has been removed from the curriculum?
It's taught in the intro data structures course at Queen's University in Ontario. Really cool stuff.