Compressed Bloom Filter

Проверил технологию под названием "Compressed Bloom Filter" (CBF), как одной из альтернатив обычному bloom filter (BF).




Основная идея CBF такова:
Пусть имеется BF для подсчёта n элементов с вероятностью промахов f.
Для этого BF рассчитаны: размер в битах m и количество хэш-функций k.
Задача: получить экономию по памяти и вероятность промахов не больше заданного f. Для этого нужно заменить m на z такое, что m*H(p)<=z<=m,
где
p = 1/2 -- вероятность заполнения в каждого бита фильтра единицей или нулём,
H(p) = -p * Log2(p) - (1 - p) * Log2(1 - p).

Математически доказано, что оптимальное значение z равно m*Ln(2), это даёт экономию по памяти ~30%.
Дополнительный бенефит -- это возможность использования меньшего количества хэш-функций 1<=k'<=k и, как результат, возможное увеличение производительности.
Подробные математические выкладки, графики и таблицы можно посмотреть, например, в этой презентации.
Реализация CBF ничем не отличается от обычного BF, за исключением пересчёта m (заменяем на z) и k.
Практически теория проверялась на BF со следующими параметрами:
BF
n = 1000000
f = 1%
m = 9585058 бит или 1198132 байта (определяется по формуле: -n*Ln(f) / Ln(2)^2)
k = 7 (определяется по формуле: (m / n) * Ln(2))

CBF:
n = 1000000
f = 1%
z = 6643856 бит или 830482 байта (m * Ln(2))
k = 4.6 ((z / n) * Ln(2)) -- соответственно проверялись значения 5, 4 и, на всякий пожарный случай, 3

На вход фильтра подавался миллион уникальных неупорядоченных 8-байтных значений, в результате:
BF,    k=7: 998908, f = 0.210%
CBF, k=5: 989869, f = 1.031%
CBF, k=4: 992324, f = 0.792%
CBF, k=3: 990364, f = 0.964%

Практические результаты несколько расходятся с теорией -- CBF показал худшее f по сравнению с BF, но в заданный 1% уложился.