What are Bloom filters? (2015) • Hacker News Board

Re: What are Bloom filters? (2015)

#11

Post by prashnts » Fri, Aug 05, 2016, 4:41 PM UTC

looki wrote: post #7

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' instead, which support delete operations.

[0] - https://en.wikipedia.org/wiki/Bloom_filter#Counting_filters

Re: What are Bloom filters? (2015)

#12

Post by SamHealer » Fri, Aug 05, 2016, 5:00 PM UTC

s_q_b wrote: post #2

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?

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

Re: What are Bloom filters? (2015)

#13

Post by bradleyjg » Fri, Aug 05, 2016, 5:03 PM UTC

Whenever considering a bloom filter also look at cuckoo filters. There are pros and cons of each approach.

See https://bdupras.github.io/filter-tutorial/ and http://11011110.livejournal.com/327681.html as well as the corresponding HN discussions https://news.ycombinator.com/item?id=12124722 and https://news.ycombinator.com/item?id=11795779

Re: What are Bloom filters? (2015)

#14

Post by jedberg » Fri, Aug 05, 2016, 5:05 PM UTC

Retric wrote: post #8

s_q_b wrote: post #2

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?

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

Re: What are Bloom filters? (2015)

#15

Post by pklausler » Fri, Aug 05, 2016, 5:06 PM UTC

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.

Re: What are Bloom filters? (2015)

#16

Post by geophile » Fri, Aug 05, 2016, 5:13 PM UTC

He takes a long time to get to the point, doesn't he?

Re: What are Bloom filters? (2015)

#17

Post by drchickensalad » Fri, Aug 05, 2016, 5:18 PM UTC

pklausler wrote: post #15

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?

Re: What are Bloom filters? (2015)

#18

Post by bostonpete » Fri, Aug 05, 2016, 5:23 PM UTC

prashnts wrote: post #11

looki wrote: post #7

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…

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.

Re: What are Bloom filters? (2015)

#19

Post by bostonpete » Fri, Aug 05, 2016, 5:30 PM UTC

s_q_b wrote: post #2

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?

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

Re: What are Bloom filters? (2015)

#20

Post by warrenmar » Fri, Aug 05, 2016, 5:30 PM UTC

Understanding Bloom filters helps you understand Count-min sketch. https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch