Show HN: BoomFilters – Probabilistic data structures for processing streams

https://github.com/tylertreat/BoomFilters

by tylertreat • 11 years ago

70 13 11 years ago

natch• 11 years ago

Why does the readme use Boom and Bloom interchangeably? Is it just a typo that for some reason is randomly scattered throughout the document (and in the repo name itself)? Or is there meant to be a difference? I don't see anywhere that the difference is explained, if it's intentional.

lstamour• 11 years ago

Looks consistently used to me. The project is a collection of stream-optimized bloom filters and the project or its filters, as a whole, are referred to as "Boom Filters" in comparison to the "Classic Bloom Filters" referenced in the paragraph directly above. Basically, use "bloom" except when referring to this exact source code or library name.

See also: references section at the bottom of the readme for background on bloom filters, examples, etc.

hurin2• 11 years ago

// The InverseBloomFilter may report a false negative but can never report a false positive.

This is actually not true and not possible. There is a good explanation here: http://cstheory.stackexchange.com/a/14455/43

There will be a low probability of false positives ~ 2^32*k. (Also it's not an inverse-bloom filter, it's a cache).

frankmcsherry• 11 years ago

Well, I'm looking at the code and it looks like it doesn't report false positives. I understand that you expect it to hash the content down and store only the hash, but it doesn't do that.

EDIT: I suppose my point was just that there is a difference between "I think you chose a bad name for your class" and "This is actually not true and not possible". It seems both true and possible (and arguably inappropriately named).

zeeboo• 11 years ago

Then it doesn't do it in constant space. Constant space is the property that makes it not a true inverse bloom filter, and instead is just a cache with an interesting hashed based eviction method.

That said, this is just a silly definition issue. You can provide a data structure with no false positives, and some false negatives, but you can't do it in constant space. I'm not aware of if you can absolutely bound the rate of false negatives.

im3w1l• 11 years ago

His answer hints at an interesting solution: For a small element store it. For a big element do nothing.

eternalban2• 11 years ago

I have a hash thing I'm working on that spills well over the Ln caches, so hitting the alternative buckets (its a linear prober) is a non-starter. Turns out the probabilities for an item ending up in an alternative bucket is in the 0.0n% range.

3 bits end up doing what would require a multiword bloom filter with 30 k hashes.

filipncs• 11 years ago

If it's a cache, there is no chance of false positives.

cbsmith• 11 years ago

It's subtly different from a cache. http://www.somethingsimilar.com/2012/05/21/the-opposite-of-a...

wcdolphin• 11 years ago

That InverseBloomFilter sounds like an LRU cache of hashes. A true inverse bloom filter can be proven to be impossible, sadly.

eternalban2• 11 years ago

You should checkout Tyler's blog. Good solid content for the concurrency geeks.

Analog24• 11 years ago

With enough data, a traditional Bloom filter "fills up", after which it has a false-positive probability of 1.

I don't think this correct. The false-positive probability wouldn't become 1, it's just that every query would return positive, regardless if it's a true or false positive. I think what you meant to say was that the positive probability is 1, not the false-positive probability.

Show HN: BoomFilters – Probabilistic data structures for processing streams

Related Stories