Real-time bidding требует real-time аналитики. RuTarget обрабатывает миллиард запросов на показ баннеров в день. Как определить, например, сколько в этих запросах уникальных пользователей? Доступно расскажем о рандомизированных алгоритмах потоковой обработки данных, вероятностных структурах данных и объясним, как быстро и с вычислительной точки зрения дешево получить нужный результат.
Основные тезисы
1) Какие данные у нас есть, и почему их много?
2) Trade-off: точность vs. нагрузка на инфраструктуру.
3) Вероятностные структуры данных для data mining - что это такое?
4) HyperLogLog - метод подсчета числа уникальных элементов в потоке данных.
5) Large scale, временное окно.
6) Примеры из реальной жизни.
7) Count-Min, Summary-Sketch и т.д.
English version