Кое-что о вероятностных структурах данных Бэкенд, теория программирования

Доклад принят в программу конференции
Павел Айткулов
piano.io

Scala data engineer.

Тезисы

Вероятностные структуры данных позволяют значительно экономить на памяти для таких запросов, как поиск количества уникальных объектов, вхождение объекта, подсчет конкретного объекта. При этом используется на 1-2 порядка меньше памяти (в некоторых задачах вообще константный объем), чем на хранение исходных данных. Как недостаток, мы иногда контролируемо ошибаемся, например, с ошибкой 10^{-9}.

Рассмотрим классические HyperLogLog, BloomFilter, CountMinSketch, как это устроено внутри и математику, использование для простейшего KV-хранилища, хранения "лайков", количества просмотров и уникальных, ротацию всего этого во времени.

Организация системы кеширования
,
Архитектурные паттерны
,
Оптимизация производительности
,
Распределенные системы
,
Алгоритмы и их сравнение

Другие доклады секции Бэкенд, теория программирования