Plots the size of a Bloom filter as a function of the expected number of elements for various false-positive rates.

bf-size.R

library(ggplot2)
library(reshape)
library(scales)

# Computes the number of kB a basic bloom filter requires.
# n:  the number of elements to store
# fp: the desired false positive rate
space = function(n, fp) { -n * log(fp) / log(2)^2 / 8 / 1024 }

N = 10^(1:9)
FP = 10^-(1:6)
x = melt(sapply(N, function(i) sapply(FP, function(j) space(i, j))))
names(x) = c("fp", "n", "value")

g = ggplot(x) +
    aes(x=n, y=value, group=factor(fp), color=fp) +
    geom_point() +
    geom_line() + 
    scale_x_continuous(breaks=log10(N), labels=math_format(10^.x)) +
    scale_y_log10(breaks=10^(-3:6), labels=comma) +
    scale_color_continuous(name="FP rate", labels=math_format(10^-.x)) +
    labs(x="Number of unique elements", y="Size (kB)")

ggsave("bf-size.png", g)