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

Re: What are Bloom filters? (2015)

#11

Post by politician » Wed, Sep 21, 2016, 11:50 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

Organizing Bloom filters into (e.g. daily) shards allows for deletion without much trouble.

Re: What are Bloom filters? (2015)

#12

Post by lanna » Thu, Sep 22, 2016, 12:47 AM UTC

I really liked Daniel Spiewak article about it: http://www.codecommit.com/blog/scala/bloom-filters-in-scala

Re: What are Bloom filters? (2015)

#13

Post by catnaroek » Thu, Sep 22, 2016, 1:20 AM UTC

gumby wrote: post #10

_ao789 wrote: post #5

Earlier quoted context omitted.

To understand recursion, you must first understand recursion.

While to understand iteration, just keep studying until you're done.

But you still need to use recursion to prove that, in fact, you will eventually be done.

Re: What are Bloom filters? (2015)

#14

Post by krat0sprakhar » Thu, Sep 22, 2016, 1:32 AM UTC

Like most devs, I too bit the bullet and wrote my version - http://prakhar.me/articles/bloom-filters-for-dummies/

Re: What are Bloom filters? (2015)

#15

Post by hinkley » Thu, Sep 22, 2016, 1:46 AM UTC

catnaroek wrote: post #13

gumby wrote: post #10

Earlier quoted context omitted.

While to understand iteration, just keep studying until you're done.

But you still need to use recursion to prove that, in fact, you will eventually be done.

Halt! I see a problem.

Re: What are Bloom filters? (2015)

#16

Post by pjscott » Thu, Sep 22, 2016, 2:05 AM UTC

hinkley wrote: post #15

catnaroek wrote: post #13

Earlier quoted context omitted.

But you still need to use recursion to prove that, in fact, you will eventually be done.

Halt! I see a problem.

You should halt if and only if you know you'll never halt.

Re: What are Bloom filters? (2015)

#17

Post by triplesec » Thu, Sep 22, 2016, 2:20 AM UTC

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 Explains Technology to a Woman'. Come on, if you're going to add entropy to our data, don't make it reinforce yet another stereotype.

Re: What are Bloom filters? (2015)

#18

Post by dlhavema » Thu, Sep 22, 2016, 2:56 AM 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

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

Re: What are Bloom filters? (2015)

#19

Post by [deleted] » Thu, Sep 22, 2016, 3:49 AM UTC

pjscott wrote: post #16

hinkley wrote: post #15

Earlier quoted context omitted.

Halt! I see a problem.

You should halt if and only if you know you'll never halt.

[deleted]

Re: What are Bloom filters? (2015)

#20

Post by catnaroek » Thu, Sep 22, 2016, 4:25 AM UTC

hinkley wrote: post #15

catnaroek wrote: post #13

Earlier quoted context omitted.

But you still need to use recursion to prove that, in fact, you will eventually be done.

Halt! I see a problem.

By “recursion”, I didn't mean a “recursive algorithm”, but rather “induction on the loop counter” (a proof technique). Since proofs aren't meant to “run”, they don't need to “halt”.