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

Word-Aligned Bloom Filters

lemire.me

Post reply on HN
Print view View original

11–20 of 82 posts

Re: Word-Aligned Bloom Filters

#11

Post by marginalia_nu »

PragmaticPulp wrote: post #7
marginalia_nu wrote: post #3

This seems a bit like a solution in search of a use case. There are simpler solutions for this particular usecase. Let's take an extreme case: You have 250 million paying customers you want to cache access to. Yeah, that's way more than you probably have, but the point is that you can keep 250 million integers in memory no problem what so ever. It fits in a gigabyte. There are raspberry pis with eight times that amou…

Obviously you don't need bloom filters if lookups are cheap, but you're ignoring all of the cases where lookups aren't cheap. You can't always put the entire database of everything in memory. Consider cases where the check is done client-side and requires a network request. A bloom filter could allow you to optimize away a network request in some, though not all, cases.

I'm curious if you have a concrete example of a case where lookups aren't cheap and a bloom filter can solve the problem.

In general, bloom filters are mainly useful for the sort of data where lookups are cheap, that is, testing for membership of a set, and that is typically one of the operations a database does really well.

In most cases where you just want to save a network roundtrip, a LRU cache is often a lot easier to get right and is much easier to keep consistent against mutable data.

Re: Word-Aligned Bloom Filters

#12

Post by lelandfe »

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters?

I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

Re: Word-Aligned Bloom Filters

#13

Post by k2xl »

marginalia_nu wrote: post #3

This seems a bit like a solution in search of a use case. There are simpler solutions for this particular usecase. Let's take an extreme case: You have 250 million paying customers you want to cache access to. Yeah, that's way more than you probably have, but the point is that you can keep 250 million integers in memory no problem what so ever. It fits in a gigabyte. There are raspberry pis with eight times that amou…

a good use case is malicious URL detection for browsers. they can look up locally and get a sense whether the url is bad and then double check against webserver.

Re: Word-Aligned Bloom Filters

#14

Post by spenczar5 »

marginalia_nu wrote: post #11
PragmaticPulp wrote: post #7

Earlier quoted context omitted.

Obviously you don't need bloom filters if lookups are cheap, but you're ignoring all of the cases where lookups aren't cheap. You can't always put the entire database of everything in memory. Consider cases where the check is done client-side and requires a network request. A bloom filter could allow you to optimize away a network request in some, though not all, cases.

I'm curious if you have a concrete example of a case where lookups aren't cheap and a bloom filter can solve the problem. In general, bloom filters are mainly useful for the sort of data where lookups are cheap, that is, testing for membership of a set, and that is typically one of the operations a database does really well. In most cases where you just want to save a network roundtrip, a LRU cache is often a lot eas…

I use them in astronomical data indexing when doing cross-match searches. That is, “could there be a star or other moving object in within 0.5 arcsec of this point in the sky?” Sky catalogs have many billions of objects but the density per solid angle of the sky is extremely variable, and moving objects also make lookups really complicated. Sky catalogs are big enough that they are not storable in memory, and may be in big Parquet tables on the network, so the full lookup is quite expensive.

Bloom filters are great for this because the backing dataset changes extremely slowly, like a few times a year when a survey publishes a new data release.

Re: Word-Aligned Bloom Filters

#15

Post by perihelions »

Oh, that's elegant.

If I math right, setting 5 bits in a 64-bit word extends the effective length of the hash function by approximately (5-1) * log_2(64) = (5-1) * 6 = 24 bits. In a simple bloom filter of storage size m bits, the hash functions have length log_2(m). All else being equal, the number of hash functions used -- hence the number of memory reads per lookup -- gets reduced by a factor of log_2(m) / [24 + log_2(m)].

(But it's not exactly equal; the storage size m has to go up by a factor of 1.2 (in the OP parameter set), for constant false-positive rate).

Re: Word-Aligned Bloom Filters

#16

Post by stevenguh »

lelandfe wrote: post #12

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

Try watching this video: https://youtu.be/Bay3X9PAX5k

Re: Word-Aligned Bloom Filters

#17

Post by avinassh »

lelandfe wrote: post #12

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

try this? - https://llimllib.github.io/bloomfilter-tutorial/

Re: Word-Aligned Bloom Filters

#18

Post by [deleted] »

marginalia_nu wrote: post #3

This seems a bit like a solution in search of a use case. There are simpler solutions for this particular usecase. Let's take an extreme case: You have 250 million paying customers you want to cache access to. Yeah, that's way more than you probably have, but the point is that you can keep 250 million integers in memory no problem what so ever. It fits in a gigabyte. There are raspberry pis with eight times that amou…

[deleted]

Re: Word-Aligned Bloom Filters

#19

Post by [deleted] »

lelandfe wrote: post #12

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

[deleted]

Re: Word-Aligned Bloom Filters

#20

Post by jefftk »

marginalia_nu wrote: post #11
PragmaticPulp wrote: post #7

Earlier quoted context omitted.

Obviously you don't need bloom filters if lookups are cheap, but you're ignoring all of the cases where lookups aren't cheap. You can't always put the entire database of everything in memory. Consider cases where the check is done client-side and requires a network request. A bloom filter could allow you to optimize away a network request in some, though not all, cases.

I'm curious if you have a concrete example of a case where lookups aren't cheap and a bloom filter can solve the problem. In general, bloom filters are mainly useful for the sort of data where lookups are cheap, that is, testing for membership of a set, and that is typically one of the operations a database does really well. In most cases where you just want to save a network roundtrip, a LRU cache is often a lot eas…

What about https://developers.google.com/safe-browsing?

In the normal case, when a website is not matched by the filter, you save a network request. This is good for both latency and privacy.

Post reply on HN