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

What are Bloom filters?

medium.com

Post reply on HN
Print view View original

21–30 of 40 posts

Re: What are Bloom filters?

#21

Post by shostack »

Anyone happen to have a great Bloom filter tutorial in Ruby geared towards early programmers?

I read the article, but am still not grasping the full construct and how it functions. I'm hoping a hands on tutorial might give me a better sense.

Re: What are Bloom filters?

#22

Post by dustingetz »

jasode wrote: post #13

>To understand Bloom filters, you first have to understand hashing. As pedagogy, I think this is the wrong approach. The author already knows Bloom filters and therefore, it seems like the most logical thing to first talk about is hash functions because that's how it's implemented . Unfortunately, that's not how a person brand new to the concept thinks about it. The first thing to talk about is motivations and scenar…

wow yes, this is an issue with nearly every technical conference talk

Re: What are Bloom filters?

#24

Post by joeldg »

bbcbasic wrote: post #4

Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?

spellcheckers use them, any time you see a company with millions of users let you know your email address was already registered, domain name registrars use them -- basically anything with a large search space where you need to know if something is in (or not) the dataset. They are useful all over. I wrote a modified version of bloom filters so the filter files are about 1/3rd the size (but with a slight cpu tradeoff) for a domain name registrar. They are kind of a staple of computer science.

Re: What are Bloom filters?

#25

Post by baddox »

jasode wrote: post #13

>To understand Bloom filters, you first have to understand hashing. As pedagogy, I think this is the wrong approach. The author already knows Bloom filters and therefore, it seems like the most logical thing to first talk about is hash functions because that's how it's implemented . Unfortunately, that's not how a person brand new to the concept thinks about it. The first thing to talk about is motivations and scenar…

I'm fine with explaining the motivation first, but I struggle to see how you can explain bloom filters without eventually getting to hashing. Obviously you don't need to explain any actual real-world hash function, but you need to explain the concept of deterministically mapping X bits to Y bits where X > Y, which is essentially what a hash function does.

Re: What are Bloom filters?

#27

Post by pronoiac »

bbcbasic wrote: post #4

Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?

I've used them before. I ran a Squid proxy and connected it to the NLANR cache hierarchy[1]; despite the name, it's more of a mesh with siblings. For the best speed, you can use bloom filters (or cache digests, in their terms[2]) to avoid the extra latency of a request of "hey, do you have this URL cached?" from someone who definitely doesn't.

[1] http://wiki.squid-cache.org/Features/CacheHierarchy

[2] http://wiki.squid-cache.org/SquidFaq/CacheDigests

Re: What are Bloom filters?

#28

Post by bru_ »

Is anybody else irritated with the incredibly tryhard tone in this article? "venison glazed in honey, served with a sweet potato hash"? Seriously??? It's an article about bloom filters for god's sake, not Leveraged Sell Out for the tech industry...

Re: What are Bloom filters?

#29

Post by FellowMarketer »

baddox wrote: post #25
jasode wrote: post #13

>To understand Bloom filters, you first have to understand hashing. As pedagogy, I think this is the wrong approach. The author already knows Bloom filters and therefore, it seems like the most logical thing to first talk about is hash functions because that's how it's implemented . Unfortunately, that's not how a person brand new to the concept thinks about it. The first thing to talk about is motivations and scenar…

I'm fine with explaining the motivation first, but I struggle to see how you can explain bloom filters without eventually getting to hashing. Obviously you don't need to explain any actual real-world hash function, but you need to explain the concept of deterministically mapping X bits to Y bits where X > Y, which is essentially what a hash function does.

I don't think at the level of the article that it's inappropriate to assume that the reader is at least familiar with the term "hashing", and can wait on the technical details of the particular types of hashing functions needed for bloom filters until the second or third section.

I honestly just closed the article when he started in on hashing, because I want to know about bloom filters (which I don't know about), not the basics of hashing (which I learned as an undergrad, and need to know day-to-day as a working programmer).

Post reply on HN