I read about halfway into this article, and when the author started talking about Javascript, the "this" keyword, and the politics about the job, I stopped.
What does that have to do with bloom filters? Get to the point!
What are Bloom filters? (2015)
41–50 of 71 posts
Re: What are Bloom filters? (2015)
#42Earlier quoted context omitted.
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.
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.
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...
Re: What are Bloom filters? (2015)
#43Bloom 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?
> 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.
Did you go to MIT, or did you, like me, attend a college that copied MIT?
Re: What are Bloom filters? (2015)
#44Bloom 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 lookin…
Shouldn't this be a problem we can apply SSE or other vector operations to? It seems like an insufficiently explored avenue.
Re: What are Bloom filters? (2015)
#45If you like hash functions and Bloom filters, you'll also enjoy Jon Bentley's description of the original UNIX spell(1) utility, which ran in 64KB by representing its dictionary as a sparse bitmap.
I did something like that in my "Obvious password detector"[1] in 1984. This is for use in password-changing programs, to detect if a password is too obvious. It uses a 3D array of bits, 27x27,27, representing trigraphs seen in the UNIX dictionary, plus a few extras such as "aaa", "bbb", etc. Only about 30% of the possible trigraphs are used in English, so most strings that aren't a word will pass. This provides simple protection against most dictionary attacks.
Re: What are Bloom filters? (2015)
#46Earlier quoted context omitted.
No, it isn't. The problem here would be that you'd be essentially invalidating arbitrary hashes from the table with each operation where they share the same "row" (or address in a bitmap) with other hashes. Suppose we have a table such that "foo", "bar", "baz" all have overlapping entry -- if we attempt to remove any of them, we'd remove the rest also. This being said, you might be interested in `Counting filter' ins…
I don't see how those could work. Since bloom filters can have false positives, the counting filter could end up letting you remove an item that was never added, thereby corrupting the entries for other items in the process.
You're right. However, in cases where we know the maximum number of items we'd be storing, we can adjust the "bucket size" of each row. Quoting the above wiki link:
> Because the counting Bloom filter table cannot be expanded, the maximal number of keys to be stored simultaneously in the filter must be known in advance. Once the designed capacity of the table is exceeded, the false positive rate will grow rapidly as more keys are inserted.
Re: What are Bloom filters? (2015)
#47Earlier quoted context omitted.
At Reddit's size, wouldn't that just shift the problem from looking up votes to looking up lists? Millions of users times millions of articles? Seems like a fast way to get an early "no" would still be useful.
Your looking it up once per page vs. once per comment. So, yes it might be faster, but when something takes 1% of total time speeding it up has massive diminishing returns.
Still, 1% of a very large number (I don't know Reddit's server costs) can be a large enough number to be worth pursuing.
Re: What are Bloom filters? (2015)
#48Earlier quoted context omitted.
> 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.
Did you go to MIT, or did you, like me, attend a college that copied MIT?
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...
Re: What are Bloom filters? (2015)
#49I read about halfway into this article, and when the author started talking about Javascript, the "this" keyword, and the politics about the job, I stopped. What does that have to do with bloom filters? Get to the point!
the post is how he's returning a favor, which he explains in the post, in the "returning the favor" section
Re: What are Bloom filters? (2015)
#50Earlier quoted context omitted.
>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. 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…
> How? 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 look…
But that requires like entirely rearchitecting the reddit backend to be less efficient.
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.