Then I remembered my old friend The Web, and sure enough a search for an equation solver uncovered this site. Very useful - enter in a linear equation, and the variable you want to solve for, et voila!
For example, from the paper above, the false negative rate is given by
fn = 1 - (1 - s/(p1 * m))^k
where fn is the false negative rate, s = the number of bits reset, p1 is the probability a given bit is set in the filter after all n elements have been added to it (about 1/2 for an optimized filter), m is the size of the filter, and k is the number of hash functions.
I wanted to know what s is, the number of bits to reset, if I know the other values. So I entered in the equation above to the equation solver, and like magic, I have
s = (1-(1-fn)^(1/k))*m*p1
Nice!
s = (1-(1-fn)^(1/k))*m*p1
Nice!
BTW, once I have the numbers worked out to my satisfaction, I'll post them here.
No comments:
Post a Comment