HyperLogLog: теория и анализ результатов

Теоретическая сводка (что считаем «нормой»)

HyperLogLog (HLL) оценивает число уникальных объектов в потоке. Для каждого элемента берётся хеш, затем:

• выбирается регистр по b битам (m = 2^b);
• по оставшимся битам считается rho (число ведущих нулей + 1);
• регистр хранит максимум rho.

Базовая оценка:

E = alpha_m * m^2 / sum(2^{-M[j]})

В этом проекте мы сравниваем эмпирическую стабильность (std относительной ошибки) с этими границами.

Анализ результатов: стандартный HLL

Источники данных:

• cmake-build-debug/results/hll_sweep_summary.csv (или results/hll_sweep_summary.csv)
• графики: python scripts/plot_hll.py (График №1 и №2)

Конкретные утверждения по точности и стабильности

По файлу hll_sweep_summary.csv (столбцы mean_rel_err, std_rel_err, rmse_rel_err):

• Лучшая константа B (число регистров m), выбранная автоматически: m = 4096, потому что имеет минимальный rmse_rel_err = 0.008943 (≈ 0.894%).
• Смещение (bias) при m=4096 практически отсутствует: mean_rel_err = -0.000125 (≈ -0.0125%).
• Стабильность при m=4096 укладывается в обе теоретические рамки: std_rel_err = 0.008943 1.042/√4096 = 0.016281, 1.32/√4096 = 0.020625 0.008943 < 0.016281 < 0.020625, т.е. укладывается.

Какая константа alpha использована (и почему)

В main.cpp используется стандартный набор alpha_m:

• alpha_16 = 0.673, alpha_32 = 0.697, alpha_64 = 0.709
• для больших m: alpha_m = 0.7213 / (1 + 1.079/m)

Эти константы выбраны так, чтобы минимизировать смещение базового оценивателя; это согласуется с наблюдаемым малым bias при больших m (см. mean_rel_err в sweep и близость линий на Графике №1).

Анализ результатов: улучшенный HLL (packed/bitmap 6-bit)

Источники данных:

• cmake-build-debug/results/hll_sweep_summary_packed.csv (или results/hll_sweep_summary_packed.csv)
• графики: python scripts/plot_hll_packed.py (График №1 и №2)

Конкретные утверждения по точности и стабильности

• Лучшая константа B (число регистров m) для packed по минимальному RMSE: m = 2048, потому что rmse_rel_err = 0.014642 (≈ 1.464%).
• Bias при m=2048 малый: mean_rel_err = 0.007797 (≈ 0.780%).
• Стабильность при m=2048 укладывается в обе теоретические рамки: std_rel_err = 0.012394 1.042/√2048 = 0.023033, 1.32/√2048 = 0.029167 0.012394 < 0.023033 < 0.029167, т.е. укладывается.

Важно: packed-вариант меняет только формат хранения регистров, а не математику оценки. Поэтому ожидается сопоставимая точность

Улучшение потребления памяти (измерение «в байтах» для регистров)

Считаем память только под регистры, без накладных расходов контейнеров:

• baseline (std::vector<uint8_t>): примерно m байт
• packed6 (6 бит/регистр): примерно ceil(6*m/8) байт

Следствие: packed использует примерно 75% памяти baseline → экономия около 25% на регистрах.

Примеры:

• при m=2048: baseline ≈ 2048 B, packed ≈ 1536 B → экономия 512 B (25%)
• при m=4096: baseline ≈ 4096 B, packed ≈ 3072 B → экономия 1024 B (25%)

Структура проекта

main.cpp

• MurmurHash32: 32-битный хеш.
• RandomStreamGen: генерация потоков случайных строк.
• ExactCounter: точный счетчик уникальных.
• HyperLogLog: базовый HLL.
• HyperLogLogPacked: улучшенный HLL с упаковкой регистров (bitmap/bitpacked, 6 бит на регистр).
• main():
  • эксперимент распределения хеша;
  • sweep по m и выбор лучшего;
  • финальные запуски на разных размерах потоков;
  • вывод CSV в results/.

Python-скрипты

• scripts/plot_hash_distribution.py — распределение бакетов хеша.
• scripts/plot_hll.py — графики №1/№2 для best m, плюс гистограмма регистров.
• scripts/plot_hll_packed.py — графики №1/№2 и гистограмма для packed-варианта.
• scripts/plot_hll_register_hists.py — распределение регистров по всем m.

Запуск

1. Запустите C++ программу (в CLion или через build) → CSV сохраняются в results/ или cmake-build-debug/results/.
2. Установите зависимости Python:

pip install -r requirements.txt

3. Постройте графики:

python scripts/plot_hash_distribution.py
python scripts/plot_hll.py
python scripts/plot_hll_packed.py
python scripts/plot_hll_register_hists.py