Data sketches — быстро, дешево и (почти) точно!

Доклад о дата-скетчах, или потоковых алгоритмах обработки и анализа данных (HyperLogLog, CPC, Theta, Count-min, FDT, KLL и других), предназначенных для решения круга задач (подсчет уникальных элементов, распределение элементов, определение их частоты и т. д.), в которых получение точных результатов требует значительных затрат вычислительных ресурсов и времени.

Если приблизительные результаты допустимы, то дата-скетчи позволяют получить их значительно быстрее традиционных вариантов. При этом в случае пакетной обработки данных альтернатив часто может не быть, а в случае потоковой обработки данных скетчи — единственное жизнеспособное решение.