Лекция 12. Вероятностные алгоритмы

Что делать, если данных о-о-очень много, а ответ на задачу нужно получить прямо сейчас? Например, вы программируете ютуб, и вам надо показать количество уникальных просмотров ролика «Despacito». В этом случае сойдут алгоритмы, которые дают лишь примерный ответ, или алгоритмы, которые дают правильный ответ только с какой-нибудь вероятностью. Оказывается, есть целый класс алгоритмов, позволяющих получить такой ответ, сэкономив просто огромное количество памяти и иногда времени. Если вы слышали такие названия как HyperLogLog, фильтр Блума, count min sketch, и хотели узнать, как они работают, то приходите на лекцию. Субъективная сложность лекции — две теты из пяти. 04:57. HyperLogLog. Подсчёт количества уникальных элементов. 20:54. Паралельный HyperLogLog. Объединение множеств. 24:36. Оценка размера пересечения и разности нескольких множеств. 34:28. MinHash. Оценка похожести двух множеств и размера пересечения двух множеств. Коэффициент Жаккара. 47:00. Блум-фильтр. Проверка принадлежности элемента множеству. 59:15. Key-value хранилище на блум-фильтре. 01:03:00. Бор на блум-фильтре. 01:09:10. Count min sketch. Поиск количества вхождений элемента в множество.