6 ms·

What are the business use cases we use bloom filters? Some examples would be great. Thanks!

by the_arun 3y ago

ajoseps 3y ago
the article provide 2 real world examples at Akamai and Google
- samwho 3y ago
  On top of those, the Wikipedia page also has a list of examples: https://en.wikipedia.org/wiki/Bloom_filter#Examples https://en.wikipedia.org/wiki/Bloom_filter#Examples
dvirsky 3y ago
One example: I personally used it to deduplicate recently viewed ads in an app, to avoid spamming users with the same ad too much. One interesting challenge there was that we needed to make sure that the client and server encode and decode the filter exactly the same, despite being implemented in different languages.
- samwho 3y ago
  Ooh that sounds fun. Something I spent time thinking about, but wasn’t able to find a huge amount of information on, is how you could use compression alongside bloom filters. You could make enormous bloom filters that make use of run length encoding or sparse bitmaps. You sacrifice insert and lookup speed but you could make enormous bloom filters this way.
  - dvirsky 3y ago
    Bloom Filters are already lossy compression, so depending on how sparse they are I'm not sure you'll get too much benefit out of it, but maybe I'm just thinking of much, much smaller filters. BTW we ended up open sourcing that BF library that encodes and decodes filters in multiple languages, the company has been out of business for nearly a decade but the project is still out there https://github.com/EverythingMe/inbloom https://github.com/EverythingMe/inbloom
pncnmnp 3y ago
I'm not sure if it's a big deal for business, but for my bachelor's thesis, we showed how we could use a type of counting bloom filters (mentioned in the blog) known as Spectral Bloom Filters, for client-side searching on static websites. Basically, it means doing all the searching and ranking directly on the client side, without needing to send any requests to the server. https://pncnmnp.github.io/blogs/spectral-bloom-filters.html https://pncnmnp.github.io/blogs/spectral-bloom-filters.html
- samwho 3y ago
  Wow, this is extremely cool! Thank you for sharing.
sakras 3y ago
It's used a lot in databases for query processing. Specifically, if you're performing a hash join, probing the hash table is more expensive than probing the Bloom filter. If you are pretty sure you're not going to find very many matches in the hash table (i.e. the join is very selective), you can skip going into the hash table by first checking the Bloom filter.
JKCalhoun 3y ago
The first I heard of a Bloom filter was when I was tasked with implementing one in iBooks. I used a Bloom filter for search. My recollection is a little fuzzy now but as I recall, as we parsed each pagination of the ePub, we would hash or index (the first three characters of?) every word on the page. Each page got its own bitfield or some such structure to hold these hashes. When a user typed a word to search we could potentially eliminate a large percentage of the pages of the ePub. If a page had no hash matches to the hashed search term then we knew the word was not contained on the page at all. A best-case example might be searching for "Jabberwocky" in the book "Through the Looking Glass". Very likely all but one page of the ePub will fall away. As is pointed out in the article, if we did get a hash match for a page it was not a guarantee the word was there — but then we would drop down to a more standard string compare to find not only if the word truly existed on the page but where it was as well (or if it existed in multiple places on the page). The worst case was of course entering a search term like the word "the" where potentially every page would have to be exhaustively string-compared. But that kind of falls in the lap of the user — why did you search for "the"?
- pncnmnp 3y ago
  This is really interesting, thanks for sharing! I'd imagine the three-character trick would have failed on programming-based ebooks, right? With all those underscores and stuff. Do you remember the preprocessing steps you took for this? On a side note, I just spent like an hour on your blog. Fascinating stuff!
  - JKCalhoun 3y ago
    Thanks. No, I don't remember the preprocessing. WebKit, at the time, was not very good at pagination, something ePub requires. iBooks work resulted in a number of "Radars" filed against WebKit with regard to pagination. As a side effect I suspect printing a web page from Safari (who does that?) is markedly better since.

What are the business use cases we use bloom filters? Some examples would be great. Thanks!

ajoseps 3y ago

the article provide 2 real world examples at Akamai and Google

samwho 3y ago
On top of those, the Wikipedia page also has a list of examples: https://en.wikipedia.org/wiki/Bloom_filter#Examples https://en.wikipedia.org/wiki/Bloom_filter#Examples

dvirsky 3y ago

One example: I personally used it to deduplicate recently viewed ads in an app, to avoid spamming users with the same ad too much. One interesting challenge there was that we needed to make sure that the client and server encode and decode the filter exactly the same, despite being implemented in different languages.

samwho 3y ago
Ooh that sounds fun. Something I spent time thinking about, but wasn’t able to find a huge amount of information on, is how you could use compression alongside bloom filters. You could make enormous bloom filters that make use of run length encoding or sparse bitmaps. You sacrifice insert and lookup speed but you could make enormous bloom filters this way.
- dvirsky 3y ago
  Bloom Filters are already lossy compression, so depending on how sparse they are I'm not sure you'll get too much benefit out of it, but maybe I'm just thinking of much, much smaller filters. BTW we ended up open sourcing that BF library that encodes and decodes filters in multiple languages, the company has been out of business for nearly a decade but the project is still out there https://github.com/EverythingMe/inbloom https://github.com/EverythingMe/inbloom

pncnmnp 3y ago

I'm not sure if it's a big deal for business, but for my bachelor's thesis, we showed how we could use a type of counting bloom filters (mentioned in the blog) known as Spectral Bloom Filters, for client-side searching on static websites. Basically, it means doing all the searching and ranking directly on the client side, without needing to send any requests to the server. https://pncnmnp.github.io/blogs/spectral-bloom-filters.html https://pncnmnp.github.io/blogs/spectral-bloom-filters.html

samwho 3y ago
Wow, this is extremely cool! Thank you for sharing.

sakras 3y ago

It's used a lot in databases for query processing. Specifically, if you're performing a hash join, probing the hash table is more expensive than probing the Bloom filter. If you are pretty sure you're not going to find very many matches in the hash table (i.e. the join is very selective), you can skip going into the hash table by first checking the Bloom filter.

JKCalhoun 3y ago

The first I heard of a Bloom filter was when I was tasked with implementing one in iBooks. I used a Bloom filter for search. My recollection is a little fuzzy now but as I recall, as we parsed each pagination of the ePub, we would hash or index (the first three characters of?) every word on the page. Each page got its own bitfield or some such structure to hold these hashes. When a user typed a word to search we could potentially eliminate a large percentage of the pages of the ePub. If a page had no hash matches to the hashed search term then we knew the word was not contained on the page at all. A best-case example might be searching for "Jabberwocky" in the book "Through the Looking Glass". Very likely all but one page of the ePub will fall away. As is pointed out in the article, if we did get a hash match for a page it was not a guarantee the word was there — but then we would drop down to a more standard string compare to find not only if the word truly existed on the page but where it was as well (or if it existed in multiple places on the page). The worst case was of course entering a search term like the word "the" where potentially every page would have to be exhaustively string-compared. But that kind of falls in the lap of the user — why did you search for "the"?

pncnmnp 3y ago
This is really interesting, thanks for sharing! I'd imagine the three-character trick would have failed on programming-based ebooks, right? With all those underscores and stuff. Do you remember the preprocessing steps you took for this? On a side note, I just spent like an hour on your blog. Fascinating stuff!
- JKCalhoun 3y ago
  Thanks. No, I don't remember the preprocessing. WebKit, at the time, was not very good at pagination, something ePub requires. iBooks work resulted in a number of "Radars" filed against WebKit with regard to pagination. As a side effect I suspect printing a web page from Safari (who does that?) is markedly better since.