Конспект: фильтр Блума, count-min, HyperLogLog

ФИЛЬТР БЛУМА: m битов, n ключей, k функций
E[доля единиц] = 1 − (1 − 1/m)^(kn) ≈ 1 − e^(−kn/m)
p ≈ (1 − e^(−kn/m))ᵏ;  k ≈ (m/n) · ln 2,  целое выбрать из соседних
при оптимуме ожидаемая доля около 1/2, p ≈ 0,6185^(m/n)

m/n = 10:   k      1       3       7       14
            p    0,095   0,017   0,008   0,019         замер: 0,094  0,018  0,0073  0,018
1% - 9,6 бита на ключ;  0,1% - 14,4;   миллиард ключей при 1% - 1,2 ГБ
ключей вдесятеро больше расчёта:  единиц 99,9%,  p = 0,994,  ошибок в журнале нет
k значений из двух хешей:  g + i·h
удаление:  счётчики вместо битов (память ×4)  или  кукушкин фильтр (отпечатки в кукушкиной таблице)

СЧЁТЧИК МОРРИСА, основание b
событие:  c = c + 1 с вероятностью 1/bᶜ        оценка:  (bᶜ − 1) / (b − 1);   b = 2:  2ᶜ − 1
почему в среднем точно:   1/2ᶜ · 2ᶜ⁺¹ + (1 − 1/2ᶜ) · 2ᶜ = 2ᶜ + 1
b = 2:      σ ≈ 0,7·n      5000 событий:  оценки 2047 … 8191,  среднее восьми 4095
b = 1,125:  σ ≤ 0,25·n     5000 событий:  оценки 3242 … 5848,  среднее восьми 4495
k счётчиков: σ в √k раз меньше;   относительная ошибка с ростом n не убывает
шаг с вероятностью 1/2ᶜ:  c случайных битов, все нули

COUNT-MIN: d строк, w столбцов, у строки своя хеш-функция
вставка x:   C[j][hⱼ(x)] += 1 в каждой строке        оценка:  минимум по строкам
ячейка = частота + чужие частоты  ⇒  оценка ≥ истины
E[шум строки] ≤ N/w;   Марков: шум > 2N/w с вероятностью ≤ 1/2;   все строки: ≤ 1/2ᵈ
w = 2/ε,  d = log₂(1/δ)        ε = 0,1%, δ = 1%:  2000 × 7 = 14 000 счётчиков
поток 8000, таблица 4 × 200:   тяжёлые 386 → 400,  410 → 424;   редкие 2 → 16,  0 → 19
ошибка - доля ПОТОКА, не доля частоты: редким ключам оценка не годится
осторожное обновление - увеличивать только минимальные ячейки;   count sketch - со знаками и медианой

ЧИСЛО РАЗЛИЧНЫХ
хеш = случайная точка на [0, 1), одна и та же для повторов
минимум v из n точек ≈ 1/(n + 1)           оценка 1/v − 1:        2000 → 735 … 14 537
k-я по малости точка vₖ                    оценка (k − 1)/vₖ:     2000 → 1745 … 2129 при k = 50

HYPERLOGLOG, m = 2ᵖ ячеек
первые p битов хеша - номер ячейки;  ранг остатка - место первой единицы;  ячейка хранит максимум
оценка = α · m² / Σ 2^(−Mⱼ)       α ≈ 0,7213 / (1 + 1,079/m)        ошибка 1,04/√m
m = 256:  6,5%  (замер: +3,0%, −7,7%, −3,8%)      m = 16 384:  0,81%,  12 КБ
мало элементов:  n ≈ m · ln(m / V),  V - число пустых ячеек,  при оценке меньше 2,5·m
объединение - поэлементный максимум;   пересечение:  |A| + |B| − |A ∪ B|, ошибка растёт