Изменения

В целом неплохой доклад про алгоритмы семейства Data Sketches. Я так понимаю, это новое собирательное название для уже некоторое время существующего класса алгоритмов - алгоритмов — потоковых статистических алгоритмов.

TLDR - TLDR — всё это реализовано в библиотеке [https://datasketches.apache.org/ Apache DataSketches] на Java и C++, бери и юзай.

В докладе охвачены затронуты алгоритмы:* Подсчёт числа уникальных элементов в потоке(Count-Distinct): HLL (HyperLogLog), CPC (Compressed Probability Counting), Theta Sketch* * HLL: число уникальных примерно равно 2^(максимальное число идущих подряд нулей в начале хешей всех элементов + 1).** CPC: число уникальных примерно равно 2^(максимальное число идущих подряд нулей в конце хешей всех элементов, кроме хешей из всех нулей).COUNTMIN SKETCH MISRAGRIES** Theta Sketch: вроде бы это обобщение алгоритма K минимальных значений. Типа, мапим каждое значение в хеш, равномерно распределённый в диапазоне чисел (0, 1). Сохраняем K+1 минимальных значений таких хешей. После чего число уникальных будет примерно равно K/(k+1-ый минимальный хеш). Вот статья про эту тету https://github.com/apache/datasketches-website/blob/master/docs/pdf/ThetaSketchFramework.pdf* Частота встречаемости элемента: CountMin Sketch, Misra-GriesКвантили гистограммы** CountMin: берём несколько независимых хеш-функций, делаем таблицу — на каждый хеш 1 строка, и заданное K колонок. На каждое значение считаем все хеши и увеличиваем на 1 соответствующую хешу колонку в строчке этого хеша. Потом, чтобы оценить частоту встречаемости элемента, берём минимум от значений ячеек, соответствующих всем его хешам.** Misra-Gries: по ходу подсчёта сохраняем K самых часто встречаемых элементов и считаем их частоты. Если же встречаем элемент, не входящий в K, увеличиваем на 1 отдельный счётчик «всех остальных», уменьшаем на 1 все частоты K элементов, удаляем элементы с нулевыми частотами. Далее частоту встречаемости любого элемента принимаем за (счётчик «всех остальных» + счётчик самого элемента).Mank * Квантили/гистограммы: куча странных названий, я себе из всего выписал Manku-Rajagopalan -Lindsay Идея(MRL), но в суть расчёта докладчик уже не погружался.