3 ms·

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 d

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.

marginalia_nu 5y ago
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.
- spenczar5 5y ago
  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.
  - marginalia_nu 5y ago
    Then we're indeed back in the territory of useful use cases, typically characterized by data that is far bigger than the system memory.
    - gpderetta 5y ago
      Bloom filter generally are much smaller than the data they represent. So if your set fits on disk, the bf might fit in ram; if your data fits in ram, your bf might fit in L3 and so on. Edit: in particular you might want to use bloom filters fir early rejects, when most of the set ownership queries are expected to fail.
- jefftk 5y ago
  What about https://developers.google.com/safe-browsing 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.
- Gh0stRAT 5y ago
  Imagine you're making a web browser plugin that blocks ads, or malicious sites. Let's assume the blocklist is a hundred megs (easily fits in ram) and your millions of users need to get the latest data hourly in order to keep up the latest URLs that you want to block. Rather than distributing the entire blocklist to your userbase, you can instead send a bloom filter + an allowlist of the small handful of sites which have a hash collision with one of the blocked sites. As a bonus, computing the hashes will have great branch prediction characteristics and you'll have fewer cache misses because the bloom filter is tiny and frequently accessed.
  - marginalia_nu 5y ago
    Couldn't you just send deltas if that is the case? Surely the hourly updates wouldn't be hundreds of megabytes? I just tested extracting 5 million URLs from my web crawler and it was like 150 Mb in plain text. That's ignoring how easy it is to create compression schemes for URLs that slash their memory footprint by something like 80%.
    - Gh0stRAT 5y ago
      Yes, you could do it with deltas instead. The tradeoffs are that it won't be as fast and will cost you a LOT more in bandwidth. (and cost your users more bandwidth as well. They might be on a very slow/limited data plan) Maybe you don't care about bandwidth and would prefer to avoid the complexity and maintenance overhead of adding a bloom filter. As with anything, there are tradeoffs and your requirements can change over time. Maybe the ad networks or malware creators start using new domains every 10 minutes to counter your blocking system so now you have to store more data and disseminate it more frequently. As engineers, it's our job to weigh the tradeoffs between different solutions given the resources and constraints of the situation. For the situation I've outlined above, I'd at least strongly consider a bloom filter but it's certainly not the only way to do it.
      - marginalia_nu 5y ago
        > As engineers, it's our job to weigh the tradeoffs between different solutions given the resources and constraints of the situation. For the situation I've outlined above, I'd at least strongly consider a bloom filter but it's certainly not the only way to do it. We should also not gloss over that with a bloom filter can't rule out false positives, and it's really not feasible to figure out which they are. Due to the nature of hashing, you won't be able to easily come up with a list of false positives. Finding just one hash collision in a wide hash is computationally stupidly hard. > As with anything, there are tradeoffs and your requirements can change over time. Maybe the ad networks or malware creators start using new domains every 10 minutes to counter your blocking system so now you have to store more data and disseminate it more frequently. Domains cost quite a lot of money so that is still pretty unrealistic. Sure you can have CN wildcards, but you can also do wildcard matching. Actually this whole scenario is unrealistic, since you can just serve ads off a random URL. The way you would create a decent ad filter is to look for characteristics in the script itself (a bit like an antivirus program), not base it off the URL.
- la_fayette 5y ago
  Bitcoin light wallet addresses are registered with bloom filters on full nodes.

marginalia_nu 5y ago

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.

spenczar5 5y ago
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.
- marginalia_nu 5y ago
  Then we're indeed back in the territory of useful use cases, typically characterized by data that is far bigger than the system memory.
  - gpderetta 5y ago
    Bloom filter generally are much smaller than the data they represent. So if your set fits on disk, the bf might fit in ram; if your data fits in ram, your bf might fit in L3 and so on. Edit: in particular you might want to use bloom filters fir early rejects, when most of the set ownership queries are expected to fail.
jefftk 5y ago
What about https://developers.google.com/safe-browsing 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.
Gh0stRAT 5y ago
Imagine you're making a web browser plugin that blocks ads, or malicious sites. Let's assume the blocklist is a hundred megs (easily fits in ram) and your millions of users need to get the latest data hourly in order to keep up the latest URLs that you want to block. Rather than distributing the entire blocklist to your userbase, you can instead send a bloom filter + an allowlist of the small handful of sites which have a hash collision with one of the blocked sites. As a bonus, computing the hashes will have great branch prediction characteristics and you'll have fewer cache misses because the bloom filter is tiny and frequently accessed.
- marginalia_nu 5y ago
  Couldn't you just send deltas if that is the case? Surely the hourly updates wouldn't be hundreds of megabytes? I just tested extracting 5 million URLs from my web crawler and it was like 150 Mb in plain text. That's ignoring how easy it is to create compression schemes for URLs that slash their memory footprint by something like 80%.
  - Gh0stRAT 5y ago
    Yes, you could do it with deltas instead. The tradeoffs are that it won't be as fast and will cost you a LOT more in bandwidth. (and cost your users more bandwidth as well. They might be on a very slow/limited data plan) Maybe you don't care about bandwidth and would prefer to avoid the complexity and maintenance overhead of adding a bloom filter. As with anything, there are tradeoffs and your requirements can change over time. Maybe the ad networks or malware creators start using new domains every 10 minutes to counter your blocking system so now you have to store more data and disseminate it more frequently. As engineers, it's our job to weigh the tradeoffs between different solutions given the resources and constraints of the situation. For the situation I've outlined above, I'd at least strongly consider a bloom filter but it's certainly not the only way to do it.
    - marginalia_nu 5y ago
      > As engineers, it's our job to weigh the tradeoffs between different solutions given the resources and constraints of the situation. For the situation I've outlined above, I'd at least strongly consider a bloom filter but it's certainly not the only way to do it. We should also not gloss over that with a bloom filter can't rule out false positives, and it's really not feasible to figure out which they are. Due to the nature of hashing, you won't be able to easily come up with a list of false positives. Finding just one hash collision in a wide hash is computationally stupidly hard. > As with anything, there are tradeoffs and your requirements can change over time. Maybe the ad networks or malware creators start using new domains every 10 minutes to counter your blocking system so now you have to store more data and disseminate it more frequently. Domains cost quite a lot of money so that is still pretty unrealistic. Sure you can have CN wildcards, but you can also do wildcard matching. Actually this whole scenario is unrealistic, since you can just serve ads off a random URL. The way you would create a decent ad filter is to look for characteristics in the script itself (a bit like an antivirus program), not base it off the URL.
la_fayette 5y ago
Bitcoin light wallet addresses are registered with bloom filters on full nodes.