Fascinating. 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'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.
In the vast majority of situations where false negatives are okay you're much better off just caching a hash of each object traditionally