What are Bloom filters? (2015) • Hacker News Board

Re: What are Bloom filters? (2015)

#21

Post by newscracker » Thu, Sep 22, 2016, 4:42 AM UTC

triplesec wrote: post #17

I have two unlikes for this story: 1. The promoting of Medium's homepage several times in the first sentences of this anvilicious story proved annoying to me. I'd rather have a straightup explanation of why they used bloom filters for this application and context, without the condescending PR-sugar-coating which isn;t really a useful addition and only detracts from our information. 2. We could retitle this: 'Jamie Ex…

Talking about dislikes of the article, this was my second time skimming through it. The first time around, I just didn't get through it fully because even though it was just a "3 minute read" according to Medium, there was too much unrelated fluff that didn't keep me engaged in it. It seemed quite unfocused due to the writer's penchant for seemingly amusing or funny anecdotes. The second time I read it, I again skimmed through all the fluff looking for the pieces of value. This article could definitely have been written a lot better in a focused way and explained Bloom filters a lot better for the same "reading time". I'm going to search for something like that, which I'm guessing is already out there.

I generally have a dislike for articles on Medium because many that I've seen look like lightweight pieces with very little value and too many words. The way images are displayed is also kind of disturbing to me. Articles either seem to have some gawdy, blurry, shaky, seizure-causing GIFs or blurry images that come into focus only after some scrolling. In my experience, Medium was good and different when it started, and seems to have become worse in quality and presentation over time. Maybe it's a temporary phase. Maybe it's not.

Re: What are Bloom filters? (2015)

#22

Post by dmlittle » Thu, Sep 22, 2016, 5:35 AM UTC

dlhavema wrote: post #18

dmlittle wrote: post #9

Bloom filters are great, but unfortunately don't support deletions of items as a particular key might be being used by more than element in the filter and you don't know if it's same to delete. A few weeks ago, someone posted about Cuckoo Filters [1] which are like Bloom Filters but allow for key deletion. [1]: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

Isn't there a variant that uses a counter instead of a bit. If counter > 0 the flag is set?

Yes, but by using a counter you increase the size of the filter and you introduce the possibility of overflows. Let's say you use 3 bits to count (rather than 1) your filter is now x3 the size and if you end up adding more than 7 items with the same key, you'll get an overflow and your false positive rate will go up. Cuckoo filters allow for deletions while using less space than a bloom or counting filter.

Re: What are Bloom filters? (2015)

#23

Post by triplesec » Thu, Sep 22, 2016, 6:12 PM UTC

One correction of computational irrelevance for this article: Bistromathics has nothing to do with an Infinite Improbability Drive, as any fule kno. That's what powered the Heart of Gold, whish Zaphod stole. Bistromathics poweres Slartibartfast's ship, which I don't think had a clever name beyond Starship Bistromath.

https://en.wikipedia.org/wiki/Technology_in_The_Hitchhiker%2...

Re: What are Bloom filters? (2015)

#24

Post by mjevans » Thu, Sep 22, 2016, 9:52 PM UTC

dmlittle wrote: post #9

Bloom filters are great, but unfortunately don't support deletions of items as a particular key might be being used by more than element in the filter and you don't know if it's same to delete. A few weeks ago, someone posted about Cuckoo Filters [1] which are like Bloom Filters but allow for key deletion. [1]: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

You can think of the result of a bloom filter as a lossfully compressed index of the question: "Is this in the set?" which has the lossful property of sometimes falsely answering yes.

If you actually have the backing data then it's possible to re-compute a new result which excludes some items. It is also possible to confirm if an answer that was yes is actually in the set.