Show HN: PDD – Probabilistic De-Duplication of Streams with Bloom Filters
1–10 of 16 posts
Re: Show HN: PDD – Probabilistic De-Duplication of Streams with Bloom Filters
#2Fascinating. Just reading about probabilistic data structures in general, and would like to know if there is an efficient general method for generating statistics about the FN rates. Are they related to ROC curves?
Re: Show HN: PDD – Probabilistic De-Duplication of Streams with Bloom Filters
#3This looks like a neat technique, but it's bothering me slightly that 'peekDistinct' returns false if the element you're testing is distinct.
Re: Show HN: PDD – Probabilistic De-Duplication of Streams with Bloom Filters
#4This looks like a neat technique, but it's bothering me slightly that 'peekDistinct' returns false if the element you're testing is distinct.
My bad. README/Documentation error. The tests are fine though.
Re: Show HN: PDD – Probabilistic De-Duplication of Streams with Bloom Filters
#5Is this a library that does entity recognition and matching on individual elements in streams, or are the streams themselves being featurized/matched?
Re: Show HN: PDD – Probabilistic De-Duplication of Streams with Bloom Filters
#6why is ur name green
Re: Show HN: PDD – Probabilistic De-Duplication of Streams with Bloom Filters
#7why is ur name green
oh boi mine is green too
Re: Show HN: PDD – Probabilistic De-Duplication of Streams with Bloom Filters
#8Re: Show HN: PDD – Probabilistic De-Duplication of Streams with Bloom Filters
#9Is this a library that does entity recognition and matching on individual elements in streams, or are the streams themselves being featurized/matched?
This library provide probabilistic set membership test on an individual element basis as the stream progresses with a fixed bound on memory. Every call to classifyDistinct() progresses the internal history of a ProbabilisticDeDuplicator.
Traditionally, probabilistic set membership tests were accomplished by using Bloom Filters. However, Bloom Filters only work well on finite sets because as Bloom Filters age (fill up), the false positive rate approaches 1. This issue was addressed by Stable Bloom Filters which frees up space for inserts; however, this introduces false negatives.
This library contributes three implementations of de-duplication algorithms centered around Bloom Filter variants whose design and replacement strategy allows it to reach stability faster than a Stable Bloom Filter while reducing the false FNR by even several orders of magnitude.
Re: Show HN: PDD – Probabilistic De-Duplication of Streams with Bloom Filters
#10Fascinating. Just reading about probabilistic data structures in general, and would like to know if there is an efficient general method for generating statistics about the FN rates. Are they related to ROC curves?
I haven't looked into the relationship with ROC curves.
I'm not sure of an efficient general method for generating statistics. I know empirically testing the structures is the easy way. For Bloom Filters which evict old data, you can calculate the probability of FN by calculating the probability that a given element is a duplicate but reported as distinct.