4 ms·

For the uninformed like me, what is the real world application for this? This is 100% curiosity and not criticism. Basically I'm curious in plain English, what

by donatj 10y ago

For the uninformed like me, what is the real world application for this? This is 100% curiosity and not criticism. Basically I'm curious in plain English, what kind of application would use this and for what? Also, am I understanding correctly that this is simply a sort of low fidelity hash table?

allendoerfer 10y ago
Say you are writing a spider and want to determine whether you have to revisit a website today or tomorrow. The minimal chance of visiting it tomorrow instead of today even if the crawler should have visited it today is trade-off you would take instantly if it increases the look-up speed, space requirements and makes stuff like this even feasible in the first place without a huge budget. Everything related to caching when working with a huge dataset is a good use-case. Another case would be when the dataset does not fit into memory, but you need very fast lookups. Edit: To clearify, you are obviously not caching the data itself, but a flag whether to use the cache/do nothing or compute something.
sluukkonen 10y ago
Here's one example. Web browsers often use bloom filters or similar data structures to check for malicious URLs. They first check the URL against the local bloom filter, and if a match is found, they double check against an online API to make sure it wasn't a false positive. Shipping a full list of malicious URLs would be too expensive, but a bloom filter fits in a fraction of the space and can still eliminate a vast majority of the API calls.
- donatj 10y ago
  Interesting. I may in fact have a use for that.
- loeg 10y ago
  They're useful in cases like this, where the set of entries is much smaller than the total set size (e.g., all URLs). Once you approach sets with 50% membership, a bitset becomes more efficient (accuracy per space) than a bloom filter or any other probabilistic structure.
rusanu 10y ago
Bloom filters are [one of?] the most used 'negative cache' structures. Consulting a bloom filter can give a decisive answer that a key is not in a collection (ie. a key was never hashed). You can then avoid a (supposedly more expensive) lookup. I used bloom filters often in my database work. I was not familiar with cockoo filters (I am familiar with cockoo hash though), using them as a 'better bloom' seems to be a relatively new development. A quick googling found 'Cuckoo Filter: Practically Better Than Bloom' [https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf].
- rusanu 10y ago
  The paper also cites the main advantage of cockoo filters over bloom: ability to remove a key. (Vanilla) bloom require a rebuild of the entire filter if a key is removed from the set. There are more details in the paper, seems a good read (I'm going though it now)
  - logingone 10y ago
    Cuckoo. :)
irfansharif 10y ago
> For applications that store many items and target moderately low false positive rates, cuckoo filters have lower space overhead than space-optimised Bloom filters. Some possible use-cases that depend on approximated set-membership queries would be databases, caches, routers, and storage systems where it is used to decide if a given item is in a (usually large) set, with some small false positive probability. Alternatively, given it is designed to be a viable replacement to Bloom filters, it can also be used to reduce the space required in probabilistic routing tables, speed longest-prefix matching for IP addresses, improve network state management and monitoring, and encode multicast forwarding information in packets, among many other applications. from the original research paper and the repository itself, thank you for asking!
discardorama 10y ago
One could also use it to verify membership (or non-membership) in a set without having access to the set. Suppose I have a secret list of websites from whom you shouldn't load ads. I can then just publish a bloom filter which you can use in your browser to see if a web request should be allowed or not, without having access to the original list. I know this is contrived, but hopefully you get the idea.
malkia 10y ago
I work at Google, and here is where I saw most of their usage, but I haven't used them directly (yet). There are plenty of documents published outside, especially on bigtable and other structures, for example: https://www.google.com/search?q=bigtable+bloom https://www.google.com/search?q=bigtable+bloom or http://www.bing.com/search?q=bigtable+bloom http://www.bing.com/search?q=bigtable+bloom

by donatj 10y ago

allendoerfer 10y ago

Say you are writing a spider and want to determine whether you have to revisit a website today or tomorrow. The minimal chance of visiting it tomorrow instead of today even if the crawler should have visited it today is trade-off you would take instantly if it increases the look-up speed, space requirements and makes stuff like this even feasible in the first place without a huge budget. Everything related to caching when working with a huge dataset is a good use-case. Another case would be when the dataset does not fit into memory, but you need very fast lookups. Edit: To clearify, you are obviously not caching the data itself, but a flag whether to use the cache/do nothing or compute something.

sluukkonen 10y ago

Here's one example. Web browsers often use bloom filters or similar data structures to check for malicious URLs. They first check the URL against the local bloom filter, and if a match is found, they double check against an online API to make sure it wasn't a false positive. Shipping a full list of malicious URLs would be too expensive, but a bloom filter fits in a fraction of the space and can still eliminate a vast majority of the API calls.

donatj 10y ago
Interesting. I may in fact have a use for that.
loeg 10y ago
They're useful in cases like this, where the set of entries is much smaller than the total set size (e.g., all URLs). Once you approach sets with 50% membership, a bitset becomes more efficient (accuracy per space) than a bloom filter or any other probabilistic structure.

rusanu 10y ago

Bloom filters are [one of?] the most used 'negative cache' structures. Consulting a bloom filter can give a decisive answer that a key is not in a collection (ie. a key was never hashed). You can then avoid a (supposedly more expensive) lookup. I used bloom filters often in my database work. I was not familiar with cockoo filters (I am familiar with cockoo hash though), using them as a 'better bloom' seems to be a relatively new development. A quick googling found 'Cuckoo Filter: Practically Better Than Bloom' [https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf].

rusanu 10y ago
The paper also cites the main advantage of cockoo filters over bloom: ability to remove a key. (Vanilla) bloom require a rebuild of the entire filter if a key is removed from the set. There are more details in the paper, seems a good read (I'm going though it now)
- logingone 10y ago
  Cuckoo. :)

irfansharif 10y ago

> For applications that store many items and target moderately low false positive rates, cuckoo filters have lower space overhead than space-optimised Bloom filters. Some possible use-cases that depend on approximated set-membership queries would be databases, caches, routers, and storage systems where it is used to decide if a given item is in a (usually large) set, with some small false positive probability. Alternatively, given it is designed to be a viable replacement to Bloom filters, it can also be used to reduce the space required in probabilistic routing tables, speed longest-prefix matching for IP addresses, improve network state management and monitoring, and encode multicast forwarding information in packets, among many other applications. from the original research paper and the repository itself, thank you for asking!

discardorama 10y ago

One could also use it to verify membership (or non-membership) in a set without having access to the set. Suppose I have a secret list of websites from whom you shouldn't load ads. I can then just publish a bloom filter which you can use in your browser to see if a web request should be allowed or not, without having access to the original list. I know this is contrived, but hopefully you get the idea.

malkia 10y ago

I work at Google, and here is where I saw most of their usage, but I haven't used them directly (yet). There are plenty of documents published outside, especially on bigtable and other structures, for example: https://www.google.com/search?q=bigtable+bloom https://www.google.com/search?q=bigtable+bloom or http://www.bing.com/search?q=bigtable+bloom http://www.bing.com/search?q=bigtable+bloom