4 ms·

Bloom filters are ideal candidates for answering the question 'Is x _not_ in the set?'. If the answer is yes, nothing, including the item you're asking about,

Bloom filters are ideal candidates for answering the question 'Is x _not_ in the set?'. If the answer is yes, nothing, including the item you're asking about, ever hashed to that location. If the answer is no, all you know is that something hashed there, possibly your item or not.

deleted 7y ago
[deleted]
jiofih 7y ago
Which works perfectly for this case: if the answer is yes, add it to output, otherwise skip.
- reitzensteinm 7y ago
  It's not that simple. If the correctness of your program relies on the "not in set" test being accurate, you're going to need to make the filter huge, and slow. Probabilistic data structures are about trading off correctness and performance. If you try to push the correctness up to near perfect, they'll quickly stop making sense and you should just use an actual perfect algorithm instead, as the author did. Bloom filters are great for early outs, where you can save a chunk of computation on a definite negative, but still be correct in case of false positive.
  - jiofih 7y ago
    Not sure I follow. For detecting uniques all you care about is the definite negatives? Either way, the author addresses precision in his post.
    - reitzensteinm 7y ago
      False positives mean you're throwing away genuinely unique items that hash the same. If you use a 256 bit Bloom filter to process a billion items, you'll get exactly 256 results that are indeed unique. The rate of false positives you require out of the data structure is key. If your program is correct with a 20% false positive rate, you're golden. If the goal is more or less 0, look elsewhere. The author addresses precision, but not in a way that questions whether a Bloom filter is indeed the right tool for the job.
      - jiofih 7y ago
        But you don’t care about false positives, only the definite negatives! I was trying to address the fact that the top comment on the utility of a bloom filter is covered in the post.
        reitzensteinm 7y ago
        If you don't care about the false positives, you don't need a Bloom filter. Just reject everything.

deleted 7y ago

[deleted]

jiofih 7y ago

Which works perfectly for this case: if the answer is yes, add it to output, otherwise skip.

reitzensteinm 7y ago
It's not that simple. If the correctness of your program relies on the "not in set" test being accurate, you're going to need to make the filter huge, and slow. Probabilistic data structures are about trading off correctness and performance. If you try to push the correctness up to near perfect, they'll quickly stop making sense and you should just use an actual perfect algorithm instead, as the author did. Bloom filters are great for early outs, where you can save a chunk of computation on a definite negative, but still be correct in case of false positive.
- jiofih 7y ago
  Not sure I follow. For detecting uniques all you care about is the definite negatives? Either way, the author addresses precision in his post.
  - reitzensteinm 7y ago
    False positives mean you're throwing away genuinely unique items that hash the same. If you use a 256 bit Bloom filter to process a billion items, you'll get exactly 256 results that are indeed unique. The rate of false positives you require out of the data structure is key. If your program is correct with a 20% false positive rate, you're golden. If the goal is more or less 0, look elsewhere. The author addresses precision, but not in a way that questions whether a Bloom filter is indeed the right tool for the job.
    - jiofih 7y ago
      But you don’t care about false positives, only the definite negatives! I was trying to address the fact that the top comment on the utility of a bloom filter is covered in the post.
      - reitzensteinm 7y ago
        If you don't care about the false positives, you don't need a Bloom filter. Just reject everything.