21–30 of 71 posts
If 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'm fond of Concierge filtering as an easy description of how they work. I view them as a brief conversation with the front desk staff at a hotel to determine if someone is there. "Is anyone here wearing a hat? Is anyone here over 6'? Did anyone come in carrying a briefcase?"
Earlier quoted context omitted.
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…
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…
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.
If 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.
Is this in programming pearls? Otherwise where?
Brilliant! 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?
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…
(To the other person who replied: In order to delete from a counting bloom filter, or a cuckoo filter, or any other data structure that doesn't store the original item, you have to know the item that you're deleting was present. Otherwise, you have the problem you noted.)
Bloom filters originally upset me because I expected the word "Bloom" to refer to an action of the algorithm. Not so someone's name. I'm fond of Concierge filtering as an easy description of how they work. I view them as a brief conversation with the front desk staff at a hotel to determine if someone is there. "Is anyone here wearing a hat? Is anyone here over 6'? Did anyone come in carrying a briefcase?"
Brilliant! 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?
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…
PS I don't understand why my comment was downvoted, is there something wrong with asking such questions here?
Earlier quoted context omitted.
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.