6 ms·

Bloom 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

by s_q_b 10y ago

Bloom 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?

chrisseaton 10y ago
> 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.
- s_q_b 10y ago
  I'm speaking more of generalized educational practice than standardized curricula.
  - hinkley 10y ago
    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.
    - nitrogen 10y ago
      I certainly didn't get the impression that the OP's follow-up comment was trying to cover up a public display of ignorance. Rather it seemed to me that the comment about lacking a centralized curriculum was needlessly snarky and did not interpret the OP's comment charitably.
      - chrisseaton 10y ago
        My comment was genuinely trying to help explain that there isn't a single curriculum! I didn't post the telling off that followed his response!
        s_q_b 10y ago
        Fully agreed. Your comment was a fair question for clarification of what I meant by "curriculum". I thought I answered it fairly by clarifying that I meant topics generally covered by most universities in their in algorithms and data structures courses. I'm not sure of the reason for the snark in the follow up. It was a fairly straightforward question and answer.
        nitrogen 10y ago
        You are quite right. I must have conflated the tone of one comment and the text of the other in my mind when I was replying.
      - hinkley 10y ago
        I... mis-parsed the reply as saying that bloom filters haven't been part of a curriculum from which to remove it, and took it as a dig at the lack in CS curricula (which sentiment I would empathize with). When Google first brought it to light I know most of the people I had access to had never encountered Bloom Filters in their college carreers. I can think of a handful of other things we 'should have learned' in school that just never came up (and I'm not even talking about practical skills, just theory). Apologies for the mixup. Interesting to see the mix of up- and down-votes I got from this one. I wonder if some people made the same mistake I did...
dmoy 10y ago
It is not standard, and was never added to most uni programs in the first place.
Retric 10y ago
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.
- jedberg 10y ago
  The place where bloom filters really shine is doing lookups on data where most of the time the data isn't there. For example, when you load a page on reddit, it has to check for a vote on every single comment on the page to see if you voted on it. Chances are 99% of the time you didn't vote on an item. Using the built in bloom filter in Cassandra, it can very quickly tell if you voted on an item without having to hit the data store most of the time, which saves a ton of time. (As a side note, there is an extra optimization that makes things even faster -- reddit tracks the last time you voted on anything as an attribute of your user, so if the page is newer than your last vote, it just assumes you couldn't have possible voted on it, skipping the lookups altogether).
  - Retric 10y ago
    A list of votes per user per page would also work. ~90% of the time that list would be empty, if it's not your likely going to eventually need to know which specific items where voted on so might as well just load them all. Further, voting records are just not that big a data structure. Sure, it's much better than a poor implementation and might be a great optimization to bolt onto a different design, but again it's niche with minimal befits when starting from scratch. Edit: Now, I really want to know how they actually do this.
gf263 10y ago
It's taught in the intro data structures course at Queen's University in Ontario. Really cool stuff.
SamHealer 10y ago
It was covered in our DSA unit, at least when I took it a couple years back.
bostonpete 10y ago
> Isn't this standard in algorithms and data structures courses? It's not in my Cormen, Leiserson, & Rivest book, though my copy's nearly 20 years old so it could have been added in a later edition.
- hinkley 10y ago
  Did you go to MIT, or did you, like me, attend a college that copied MIT?
  - bostonpete 10y ago
    I didn't attend MIT -- why do you think it's copying MIT, because it's from MIT press? I believe that's the closest thing there is to a "standard" algorithms textbook but things may have changed since my college days...
the8472 10y ago
Bittorrent uses them for distributed calculation of statistics. For counting of set unions specifically. http://bittorrent.org/beps/bep_0033.html#abstract http://bittorrent.org/beps/bep_0033.html#abstract

by s_q_b 10y ago

chrisseaton 10y ago

> 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.

s_q_b 10y ago
I'm speaking more of generalized educational practice than standardized curricula.
- hinkley 10y ago
  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.
  - nitrogen 10y ago
    I certainly didn't get the impression that the OP's follow-up comment was trying to cover up a public display of ignorance. Rather it seemed to me that the comment about lacking a centralized curriculum was needlessly snarky and did not interpret the OP's comment charitably.
    - chrisseaton 10y ago
      My comment was genuinely trying to help explain that there isn't a single curriculum! I didn't post the telling off that followed his response!
      - s_q_b 10y ago
        Fully agreed. Your comment was a fair question for clarification of what I meant by "curriculum". I thought I answered it fairly by clarifying that I meant topics generally covered by most universities in their in algorithms and data structures courses. I'm not sure of the reason for the snark in the follow up. It was a fairly straightforward question and answer.
      - nitrogen 10y ago
        You are quite right. I must have conflated the tone of one comment and the text of the other in my mind when I was replying.
    - hinkley 10y ago
      I... mis-parsed the reply as saying that bloom filters haven't been part of a curriculum from which to remove it, and took it as a dig at the lack in CS curricula (which sentiment I would empathize with). When Google first brought it to light I know most of the people I had access to had never encountered Bloom Filters in their college carreers. I can think of a handful of other things we 'should have learned' in school that just never came up (and I'm not even talking about practical skills, just theory). Apologies for the mixup. Interesting to see the mix of up- and down-votes I got from this one. I wonder if some people made the same mistake I did...

dmoy 10y ago

It is not standard, and was never added to most uni programs in the first place.

Retric 10y ago

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.

jedberg 10y ago
The place where bloom filters really shine is doing lookups on data where most of the time the data isn't there. For example, when you load a page on reddit, it has to check for a vote on every single comment on the page to see if you voted on it. Chances are 99% of the time you didn't vote on an item. Using the built in bloom filter in Cassandra, it can very quickly tell if you voted on an item without having to hit the data store most of the time, which saves a ton of time. (As a side note, there is an extra optimization that makes things even faster -- reddit tracks the last time you voted on anything as an attribute of your user, so if the page is newer than your last vote, it just assumes you couldn't have possible voted on it, skipping the lookups altogether).
- Retric 10y ago
  A list of votes per user per page would also work. ~90% of the time that list would be empty, if it's not your likely going to eventually need to know which specific items where voted on so might as well just load them all. Further, voting records are just not that big a data structure. Sure, it's much better than a poor implementation and might be a great optimization to bolt onto a different design, but again it's niche with minimal befits when starting from scratch. Edit: Now, I really want to know how they actually do this.

gf263 10y ago

It's taught in the intro data structures course at Queen's University in Ontario. Really cool stuff.

SamHealer 10y ago

It was covered in our DSA unit, at least when I took it a couple years back.

bostonpete 10y ago

> Isn't this standard in algorithms and data structures courses? It's not in my Cormen, Leiserson, & Rivest book, though my copy's nearly 20 years old so it could have been added in a later edition.

hinkley 10y ago
Did you go to MIT, or did you, like me, attend a college that copied MIT?
- bostonpete 10y ago
  I didn't attend MIT -- why do you think it's copying MIT, because it's from MIT press? I believe that's the closest thing there is to a "standard" algorithms textbook but things may have changed since my college days...

the8472 10y ago

Bittorrent uses them for distributed calculation of statistics. For counting of set unions specifically. http://bittorrent.org/beps/bep_0033.html#abstract http://bittorrent.org/beps/bep_0033.html#abstract