4 ms·
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 positiv
by 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 agoI'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 agoIn 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