Рене Андреасович ван Беверн (Dr.rer.nat., доцент КафТК ММФ НГУ и эксперт по большим данным компании Huawei Cloud Technologies) прочитает в весеннем семестре этого учебного года спецкурс
«Алгоритмы для анализа больших объёмов данных» (спецкурс Кафедры теоретической кибернетики ММФ НГУ).
Время: по пятницам, 10:50 – 12:25
Начало: 11.02.2022
Место: онлайн (ссылки рассылаются ближе к началу занятия)
Заинтересованные студенты приглашаются присоединиться к
телеграм-каналу спецкурса
https://t.me/+RHMwJVb98U4yMmVi
Содержание
В этом курсе мы ознакомимся с алгоритмами для анализа данных, которые невозможно хранить в памяти одного компьютера. В связи с этим возникают множество проблем:
- потоковая обработка данных: алгоритм может пройти по входу всего один раз и при этом может использовать память асимптотически меньше, чем длина записи входа (например, логарифмическую память),
- распределённые вычисления: разные части входных данных хранятся на разных узлах кластера, алгоритм на каждом узле видит только часть данных, но узлы должны «договориться» об общем решении задачи. Коммуникация между узлами кластера — дорогая. Поэтому желательно передавать как можно меньше информации между ними.
- распределённое хранение данных: данные хранятся на разных узлах кластера, нужно уметь быстро находить данные по ключу, не используя централизованного индекса (который может не справиться с нагрузкой).
Такие ограничения могут усложнить даже простейшие задачи:
Пример 1: как выбрать хотя бы один случайный элемент из всего потока, с равномерным распределением? Ведь за один проход по потоку мы не можем сначала посчитать длину n потока и потом выбрать элемент со случайным индексом от 1 до n.
Пример 2: как найти хотя бы количество разных элементов в потоке? Если мы для каждого из n элементов будем хранить, видели ли мы его, то это может занять n единиц памяти, что соразмерно всему потоку. Мы увидим, как задачу решить в памяти O(log log n).
Так как наши алгоритмы никогда не видят входа целиком, большинство алгоритмов будут рандомизированными и приближёнными, то есть, они будут давать хорошее приближение с большой вероятностью. Оценки будут математически гарантированы.
Примерный список тем (буду подстраиваться под слушателей)
Введение
1. Случайная выборка из потока
2. Подсчёт разных элементов из потока
Алгоритмы обработки потоковых данных
3. Генерация случайных хэш-функций
4. Оценка частоты элементов в потоке
5. Оценка медианы потока
6. Поиск самых частых записей
7. Проверка связности и двудольности графов
8. Границы возможного: Нижние оценки требуемой памяти
Распределённые вычисления в модели MapReduce
9. Вводные примеры
10. Максимальные паросочетания
11. Минимальное остовное дерево
13. Размещение работ в кластере без централизованного планировщика.
Распределённое хранение данных
14. Фильтры блюма
15. Кукушечные фильтры
