Tuesday, October 20, 2009

Online equation solver

I'm working with Retouched Bloom Filters (PDF), and am trying to figure out how to calculate the size of a filter given a desired false positive and false negative rate. I tried to do some of the math, but I'm just too rusty.

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!

BTW, once I have the numbers worked out to my satisfaction, I'll post them here.

No comments: