Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bloom Filters for the Perplexed

sagi.io

Post reply on HN
Print view View original

11–20 of 46 posts

Re: Bloom Filters for the Perplexed

#11

Post by niftich »

mlevental wrote: post #5
oli5679 wrote: post #2

Every month or so there is a new version of an article like this posted on hn

you scoff but this is a very thorough presentation of a bloomfilter - very few of these sorts of articles actually cover the computation of the probability bounds.

Yeah, there have been a good number [1] and a steady stream of submissions about Bloom filters (and truly, the inevitable re-riff about Cuckoo filters), but this article is toward the higher end of the quality scale.

It's a bit odd that a data structure attracts this kind of attention, but not all of it is about self-discovery, and the fact that people feel writing about them belies the fact that they either consider it a novelty, or expect members of their intended audience to consider them as such. Hopefully with time, we will reach a saturation point where most people (including beginners) are familiar with Bloom filters because they've been formally taught or read one of these articles.

[1] https://hn.algolia.com/?query=bloom+filter&sort=byDate&type=...

Re: Bloom Filters for the Perplexed

#12

Post by 3131s »

bradleyjg wrote: post #6
oli5679 wrote: post #2

Every month or so there is a new version of an article like this posted on hn

I read a few of these articles a couple of years ago. Along with a few of the inevitable cuckoo hash filter rejoinders. I think they are neat algorithms and I'm glad to have come across them. But that said, I have yet to find a problem in my day to day work which required set membership, with space at a premium, and where false positives were acceptable. So I've never used either in anger.

I have used them for text segmentation. It's an extremely quick way to test for membership on a set (30+ million tokens in my case) that would otherwise be too large to hold in main memory.

Re: Bloom Filters for the Perplexed

#13

Post by foo101 »

mlevental wrote: post #5
oli5679 wrote: post #2

Every month or so there is a new version of an article like this posted on hn

you scoff but this is a very thorough presentation of a bloomfilter - very few of these sorts of articles actually cover the computation of the probability bounds.

The Wikipedia article on bloom filter is already pretty thorough and discusses the computation of the probability bounds as well as the optimal parameters: https://en.wikipedia.org/wiki/Bloom_filter

Re: Bloom Filters for the Perplexed

#14

Post by busterarm »

Jake232 wrote: post #7
bradleyjg wrote: post #6

Earlier quoted context omitted.

I read a few of these articles a couple of years ago. Along with a few of the inevitable cuckoo hash filter rejoinders. I think they are neat algorithms and I'm glad to have come across them. But that said, I have yet to find a problem in my day to day work which required set membership, with space at a premium, and where false positives were acceptable. So I've never used either in anger.

They're very useful in large scale web crawling/scraping. I use them for a number of things in this field.

Also in distributed brute-forcing of encryption standards.

Re: Bloom Filters for the Perplexed

#15

Post by arielweisberg »

bradleyjg wrote: post #6
oli5679 wrote: post #2

Every month or so there is a new version of an article like this posted on hn

I read a few of these articles a couple of years ago. Along with a few of the inevitable cuckoo hash filter rejoinders. I think they are neat algorithms and I'm glad to have come across them. But that said, I have yet to find a problem in my day to day work which required set membership, with space at a premium, and where false positives were acceptable. So I've never used either in anger.

If you are bored with bloom and cuckoo filters then check out quotient filters. Quotienting was one of those mind blown things for me.

Re: Bloom Filters for the Perplexed

#17

Post by jason_slack »

arielweisberg wrote: post #15
bradleyjg wrote: post #6

Earlier quoted context omitted.

I read a few of these articles a couple of years ago. Along with a few of the inevitable cuckoo hash filter rejoinders. I think they are neat algorithms and I'm glad to have come across them. But that said, I have yet to find a problem in my day to day work which required set membership, with space at a premium, and where false positives were acceptable. So I've never used either in anger.

If you are bored with bloom and cuckoo filters then check out quotient filters. Quotienting was one of those mind blown things for me.

Thanks for the reading list! :-)

Re: Bloom Filters for the Perplexed

#18

Post by manish_gill »

bradleyjg wrote: post #6
oli5679 wrote: post #2

Every month or so there is a new version of an article like this posted on hn

I read a few of these articles a couple of years ago. Along with a few of the inevitable cuckoo hash filter rejoinders. I think they are neat algorithms and I'm glad to have come across them. But that said, I have yet to find a problem in my day to day work which required set membership, with space at a premium, and where false positives were acceptable. So I've never used either in anger.

I use them at work as a cache during data ingestion phrase (analytics). I have to store a unique URL for each page the user is at, and each page generates a lot of requests. So I store the URLs inside a Bloom Filter, hitting the DB only when the contain() returns False. It's a neat little thing that saves me thousands of unnecessary database hits per second.

Re: Bloom Filters for the Perplexed

#19

Post by andybak »

davidivadavid wrote: post #10
lalaithion wrote: post #4

Earlier quoted context omitted.

So, bloom filters are the equivalent of Monads? https://byorgey.wordpress.com/2009/01/12/abstraction-intuiti...

They both seem like fairly easy concepts. I'm not sure why they get so much coverage.

"A monad is just a monoid in the category of endofunctors, what's the problem?"

Re: Bloom Filters for the Perplexed

#20

Post by voidmain »

Bloom filters are a nice data structure, and you should absolutely have them in your toolbox, but if you go looking for a reason to use one you are likely to wind up making things worse. The following is not valid reasoning: "Bloom filters are efficient. Therefore if I can find a way to use a bloom filter, my solution will be efficient."

The "SSH keys" protocol in the article seems like an example of this. It doesn't make any sense. Why would the server send the client a Bloom filter if the client has already told it what key it wants to check? The server only has to send one bit back to the client! And if the goal is to not trust the server with the client's (public) key, this protocol doesn't accomplish that either.

And if you do for some reason have to transmit the entire database of compromised SSH keys in a way that permits only membership tests, a Bloom filter isn't the most compact way to do it! For example, off the top of my head, you could calculate an (15+N)-bit hash for each element of the list, sort the hashes, and rice code the deltas. That would take very roughly 32768 * (N+2) bits and give about 1 in 2^N false positives. So for N=13 it is about the size of the bloom filter in the article but gives a false positive rate 8 times lower. This data structure isn't random access like a Bloom filter, but that doesn't matter for something you are sending over the network (which is always O(N)).

Post reply on HN