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.
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).
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.
Not really. People tend to vote on one or two things on a page. So you'll have a long list of people who voted on one or two of the 1000+ items, and now you've had to do an extra lookup.
It's a lot faster to just go straight for the votes and take advantage of the bloom filter.
However, it's 100% empty the first time someone opens a link. If someone up votes there is no need to refresh, so they need to up vote and then refresh the page which I assume is less common. With lot's of pages that never get refreshed and a long tail of pages people go back to. So, my assumption is you can easily keep a vote list in memory for popular pages and everything else is basically a non issue.
As to matching up votes with items, I kind of think that's for client side JavaScript in most cases.
How? This means you're now duplicating data, instead of organizing as
page has comments have comments have ... have votes
you now have
page has comments have comments have ... have votes page has list of special comments where you don't know where they are or what their parental hierarchy is and still need to look up in the list anyway.
you're duplicating the "has been voted on" field.
Page has a list of people who have voted, and that list points to a list of their votes. Each comment has a a number for vote counts, but not a list of scores.
User opens page, they get a list of comments with scores. And a possibly empty list of votes. 99.9% is probably less than 20 votes from that user so 160 bytes or less. Worst case is what 8 byte comment ID * 1,000 up-votes = 8k.
On user vote, server looks at past votes on page and adds it if missing then updates comment score.
Ok, you need every vote from each user and caching comment scores is really likely a no brainier, but I guess you could recalculate it.
PS: Not all comments are going to be loaded, but again if your sending <200 bytes for the full list 99.9% of the time then doing something else has limited value.
A page has comments a comment has comments a comment has votes a vote has a user
That is to say that a vote is a many to many join from user-comment.
To do what you want, you'd also have to give the page the concept of "people who have voted on a comment that belongs to be or one of my children"
>User opens page, they get a list of comments with scores. And a possibly empty list of votes. 99.9% is probably less than 20 votes from that user so 160 bytes or less. Worst case is what 8 byte comment ID * 1,000 up-votes = 8k.
The problem isn't sending additional data over the wire, its that, say I've voted on 500 things on a page, then we're at 250,000 operations (for each comment check if its in my list of voted on comments), whereas a bloom implementation is O(n). And also the whole making your database structure repetative and icky.
My approach that's client side most of the time. Further it's O (n) to compare matches between two sorted lists so just sort them in O (n log n). Further log 500 is faster than most hashes.
And of course for the most common case of no votes it's a single lookup and done.
PS: As to changing the back end, yes if the initial implementation is bad then you might have a point. But, again fixing the problem also works and produces far less code to maintain.
I don't think there is such a thing as a single curriculum taught by all colleges that it could have been removed from.
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.
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...
I'm not sure of the reason for the snark in the follow up. It was a fairly straightforward question and answer.
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.
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?