4 ms·

What is BloomFilter?

by chrstphrhrt 11y ago

m00dy 11y ago
well, it is a probabilistic data structure.
- chrstphrhrt 11y ago
  Ahh okay: https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter That's super interesting! I wonder what kinds of stuff you could do with that in a fancy datastore like Elasticsearch or GraphDB. If it could be mapped to a resource model in a straightforward way, it'd be fun to make a special "ORM" that plugs into an API framework to expose public services.
  - rakoo 11y ago
    Bloom filter are used to greatly reduce the amount of straw when you're looking for a needle in a haystack. Take bup (https://github.com/bup/bup/ https://github.com/bup/bup/) for instance. It splits your content into chunks and stores them into GB-sized packs. With large backups you easily end up in hundreds of packs. During the splitting process it needs to search for a hash (the needle) into the huge amount of chunks (the haystack). That's why bup has one bloom filter per pack, which means that instead of searching through hundreds of packs you will have to search through maybe 2 or 3 packs. There are false positives (you know a hash can only realistically be contained in a single pack) but it is you the developer who choose how much you want. There is some complicated math that allows you to balance false positives, size of the structure, and expected number of elements. There's a similar process inside LevelDB (http://leveldb.org/ http://leveldb.org/) and it's going to be the same thing for systems that store their data in multiple parts and know that what they're looking for actually is in a single part.
deleted 11y ago
[deleted]
fsloth 11y ago
There is also an overload of terms. In addition to the algorithmic meaning (as in this case) it's also a computer graphics technique: https://en.wikipedia.org/wiki/Bloom_(shader_effect) https://en.wikipedia.org/wiki/Bloom_(shader_effect)
mjhoy 11y ago
This is a great video that introduces the concept: https://www.youtube.com/watch?v=-SuTGoFYjZs https://www.youtube.com/watch?v=-SuTGoFYjZs
brightball 11y ago
My understanding is that it's a means of checking a dataset very quickly with a 100% chance of avoiding "false negatives" but no guarantees around false positives. Some interesting use cases around them for very high performance filtering operations, but probably overkill and overthink for the vast majority of issues out there. It's something you'd generally looking at if you were trying to performance tune a lot of checks against a big dataset.
- snerbles 11y ago
  I've used bloom filters in cross-referencing multiple data sources, where queries from one badly-optimized database were very expensive. In this case, the penalty of a false positive was merely a five-second lookup.
- KMag 11y ago
  In the Gnutella P2P protocol, searches are broadcast to the nearest neighbors in the (essentially random) graph (with a hop count to prevent infinite propagation, and keeping a list of recently seen query IDs to prevent cycles). This essentially causes a random graph with N-ary nodes to act like a tree with a branching factor of N-1. Think of it as running the spanning tree algorithm[0] for each query. (The Nth link is the link up to the parent of the node. This analysis ignores duplicate links.) Peers exchange Bloom filters of the keywords for the files they have. That way, if the hop count indicates that a query has only one more hop to live, the Bloom filters are consulted to eliminate the last hop in cases where a leaf node doesn't have any matching files. (Since Bloom filters don't have false negatives, this pruning is safe/conservative.) It might not sound like much to only save the last hop, but remember that for a tree of degree N-1, the leaves represent almost (N-2)/(N-1) portion of the nodes. So, if every peer is connected to 21 other peers, you get a 20-way tree, and a bloom filter at best can save you almost 95% of your query traffic. There's lots of simplification in the above analysis (ignoring multiple paths to the same host, etc., etc.) but you get the gist of it. (This assumes a query for some really rare keyword... the peers use sampling of their nearest neighbors to first estimate the hop count they need in order to get a target number of search results... so searches for popular keywords are unlikely to be helped by the Bloom filter, but they're also sent with a low hop count.) [0]https://en.wikipedia.org/wiki/Spanning_Tree_Protocol https://en.wikipedia.org/wiki/Spanning_Tree_Protocol

What is BloomFilter?

m00dy 11y ago

well, it is a probabilistic data structure.

chrstphrhrt 11y ago
Ahh okay: https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter That's super interesting! I wonder what kinds of stuff you could do with that in a fancy datastore like Elasticsearch or GraphDB. If it could be mapped to a resource model in a straightforward way, it'd be fun to make a special "ORM" that plugs into an API framework to expose public services.
- rakoo 11y ago
  Bloom filter are used to greatly reduce the amount of straw when you're looking for a needle in a haystack. Take bup (https://github.com/bup/bup/ https://github.com/bup/bup/) for instance. It splits your content into chunks and stores them into GB-sized packs. With large backups you easily end up in hundreds of packs. During the splitting process it needs to search for a hash (the needle) into the huge amount of chunks (the haystack). That's why bup has one bloom filter per pack, which means that instead of searching through hundreds of packs you will have to search through maybe 2 or 3 packs. There are false positives (you know a hash can only realistically be contained in a single pack) but it is you the developer who choose how much you want. There is some complicated math that allows you to balance false positives, size of the structure, and expected number of elements. There's a similar process inside LevelDB (http://leveldb.org/ http://leveldb.org/) and it's going to be the same thing for systems that store their data in multiple parts and know that what they're looking for actually is in a single part.

deleted 11y ago

[deleted]

fsloth 11y ago

There is also an overload of terms. In addition to the algorithmic meaning (as in this case) it's also a computer graphics technique: https://en.wikipedia.org/wiki/Bloom_(shader_effect) https://en.wikipedia.org/wiki/Bloom_(shader_effect)

mjhoy 11y ago

This is a great video that introduces the concept: https://www.youtube.com/watch?v=-SuTGoFYjZs https://www.youtube.com/watch?v=-SuTGoFYjZs

brightball 11y ago

My understanding is that it's a means of checking a dataset very quickly with a 100% chance of avoiding "false negatives" but no guarantees around false positives. Some interesting use cases around them for very high performance filtering operations, but probably overkill and overthink for the vast majority of issues out there. It's something you'd generally looking at if you were trying to performance tune a lot of checks against a big dataset.

snerbles 11y ago
I've used bloom filters in cross-referencing multiple data sources, where queries from one badly-optimized database were very expensive. In this case, the penalty of a false positive was merely a five-second lookup.
KMag 11y ago
In the Gnutella P2P protocol, searches are broadcast to the nearest neighbors in the (essentially random) graph (with a hop count to prevent infinite propagation, and keeping a list of recently seen query IDs to prevent cycles). This essentially causes a random graph with N-ary nodes to act like a tree with a branching factor of N-1. Think of it as running the spanning tree algorithm[0] for each query. (The Nth link is the link up to the parent of the node. This analysis ignores duplicate links.) Peers exchange Bloom filters of the keywords for the files they have. That way, if the hop count indicates that a query has only one more hop to live, the Bloom filters are consulted to eliminate the last hop in cases where a leaf node doesn't have any matching files. (Since Bloom filters don't have false negatives, this pruning is safe/conservative.) It might not sound like much to only save the last hop, but remember that for a tree of degree N-1, the leaves represent almost (N-2)/(N-1) portion of the nodes. So, if every peer is connected to 21 other peers, you get a 20-way tree, and a bloom filter at best can save you almost 95% of your query traffic. There's lots of simplification in the above analysis (ignoring multiple paths to the same host, etc., etc.) but you get the gist of it. (This assumes a query for some really rare keyword... the peers use sampling of their nearest neighbors to first estimate the hop count they need in order to get a target number of search results... so searches for popular keywords are unlikely to be helped by the Bloom filter, but they're also sent with a low hop count.) [0]https://en.wikipedia.org/wiki/Spanning_Tree_Protocol https://en.wikipedia.org/wiki/Spanning_Tree_Protocol