Алгоритмы обработки потоковых данных

Общая информация
ЛекторВ. В. Опарин
Семестросень 2014
Дата начала14.09.2014
Количество пар8
Язык курсарусский
Вопросы к экзамену
Видеоhttp://www.lektorium.tv/course/24391
Аннотация

Представим, что у нас есть большой объем данных. Данные могут быть получены с метеорологических сенсоров, это может быть интернет-трафик или, например, банковские транзакции. Какую ценную информацию мы способны извлечь в условиях, когда памяти программы имеется значительно меньше чем объема данных, которые необходимо обработать? Что, если сохранить, а потом обработать ВСЮ ценную информацию невозможно?

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

Литература

Лекционный материалы по аналогичному курсу Дармутского Колледжа
S. Muthukrishnan "Data Streams: Algorithms and Applications" (выбрать Book: pdf)

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция 1. Введение. Детерминированный поиск частых элементов
(14.09.2014 - 11:15 - 12:50)

Введение. Кассовая и турникетная модели. Рассмотрим задачу поиска частых элементов. Дано $ k $ и последовательность из $ m $ чисел. Мы построим двух-проходный алгоритм (Мисра-Граеса), который находит все элементы, встречающиеся в последовательности хотя бы $ \lfloor \frac{m}{k} \rfloor + 1 $ раз, и использует $ O(k(\log m + \log n)) $ памяти. Также покажем нижнюю линейную оценку на память для одно-проходной версии задачи.
Статья Мисра-Граеса (1982)
2. Лекция 2. Мультипроходный точный детерминированный поиск статистик
(05.10.2014 - 11:15 - 12:50)

Мы рассмотрим задачу поиска порядковых статистик в потоке и разберем детерминированные алгоритмы. Алгоритм Мунро-Патерсона находит точный ответ, но использует несколько проходов. При разрешенных $ p $ проходах алгоритм использует $ O(m^{1 \slash p} \log^{2 - 2 \slash p} m \log n) $ памяти.
Статья Мунро-Патерсона (1980)


http://www.youtube.com/watch?v=V_vaDxsIsdc
3. Лекция 3. Детерминированный приближенный поиск статистик
(12.10.2014 - 11:15 - 12:50)

Алгоритм Гринвалда-Кханна находит приближенный в отношении статистики ответ с точностью $ \pm \epsilon \cdot m $, при этом использует памяти всего $ O(\frac{1}{\epsilon} \cdot \log(\epsilon \cdot m)) $.
Статья Гринвалда-Кханна (2001)
4. Лекция 4. Число различных элементов
(19.10.2014 - 11:15 - 12:50)

Минимальный набор из тервера. 2-независимые хэш-функции. Задача подсчета различных элементов в потоке. Алгоритм Флажолета-Мартина по версии Алона-Матиаса-Сзегеди (AMS'99). Считает ответ с фиксированной погрешностью и вероятностью ошибки не более $ \delta $. Использует $ O(\log \frac{1}{\delta} \log n) $ памяти. Алгоритм BJKST'04 считает ответ с мультипликативной погрешностью $ \epsilon $ и вероятностью ошибки не более $ \delta $. У нас будет $ O(\log \frac{1}{\delta} \log n) $. Можно довести до $ O(\log n + \log \frac{1}{\delta} (\log \frac{1}{\epsilon} + \log \log n)) $.
Статья Флажолета, Мартина (1983)
Статья Алона, Матиаса, Сзегеди (1999)
Статья BJKST (2004)


http://www.youtube.com/watch?v=K64EBBKkQrg#t=679
5. Лекция 5. Приближенный поиск частых элементов. Оценка моментов
(09.11.2014 - 11:15 - 12:50)

Понятие эскиза. Оценка частот элементов через эскизы.
  • Алгоритм Чарикара-Чена-Фараха-Колтона. Для любого $ x $ выдает ответ в отрезке $ [f_x - \varepsilon \cdot ||f||_2, f_x + \varepsilon \cdot ||f||_2] $ c вероятностью $ 1 - \delta $. Память: $ O(\varepsilon^{-2} \log \delta^{-1} (\log n + \log m)) $.
  • Алгоритм Кормода-Муфукришнана. Для любого $ x $ выдает ответ в отрезке $ [f_x, f_x + \varepsilon \cdot ||f||_1] $ с вероятностью $ 1 - \delta $. Память: $ O(\varepsilon^{-1} \log \delta^{-1} (\log n + \log m)) $.
  • Алгоритм Алона-Матиаса-Сзегеди. Оценка момента $ F_2 $ через эскиз. Выдает ответ с точность $ \pm \varepsilon ||f||_2 $ c вероятностью $ 1 - \delta $. Память: $ O(\varepsilon^{-2}\log \delta^{-1} (\log n + \log m)) $
  • Алгоритм Вудраффа. Линейная регрессия при небольшом числе предикторов $ d $ на $ n $ наблюдениях. Выдает вектор коэффициентов $ \hat{x} $ такой, что $ ||A\hat{x} - b||_2 \leq (1 + \varepsilon) \min_x ||Ax - b||_2 $ с вероятностью $ 1 - \delta $. Память: $ O(d^2 \varepsilon^{-1} \log \delta^{-1} \log (nd) $.
  • Алгоритм Алона-Матиаса-Сзегеди. Оценка произвольного момента $ F_k $ при константе $ k \geq 1 $. Память $ O(\varepsilon^{-2} \log \delta^{-1} n^{1 - \frac{1}{k}} (\log m + \log n)) $.

Статья Дэвида Вудраффа (2012)
Статья Алона, Матиаса, Сзегеди (1999)
остальное можно посмотреть в конспекте Дармутского колледжа.


6. Лекция 6. Минимальные хэш-функции. Синхронизация множеств
(16.11.2014 - 11:15 - 12:50)

Сравнение множеств на равенство за $ O(\log\frac{1}{\delta} \log n) $ памяти. Семейство минимально независимых хэш-функций. Оценка символа Жаккара. Поиск числа редких элементов. Задача согласования множеств c ограниченной симметрической разностью $ O(k \log n) $.
A Small Approximately Min-Wise Independent Family of Hash Functions, Indyk, 2001
Set Reconciliation with Nearly Optimal Communication Complexity, Minsky, Trachtenberg, Zippel, 2004 http://www.youtube.com/watch?v=k5FqhjqVJNs#t=407
7. Лекция 7. Полупотоковые алгоритмы на графах. Базовые алгоритмы
(16.11.2014 - 13:00 - 14:35)

Нижняя оценка на задачу связности. Понятие полупотоковых алгоритмов. Проверка графа на связность и двудольность за один проход с СНМ. Двудольность, минимальное остовное дерево, мосты и компоненты реберной двусвязности через динамические деревья в один проход. Кратчайшие пути через $ t $-спаннер с использованием $ O(n^{1 + \frac{2}{t}}) $ памяти. Поиск взвешенного и невзвешенного паросочетания: 5.83- и 2-приближения. Поиск числа треугольников в один проход без эскиза использованием $ O(\varepsilon^{-2} (\log\frac{1}{\delta}) \frac{mn}{T}) $ памяти и с эксизом при $ O(\varepsilon^{-2} (\log\frac{1}{\delta}) (\frac{mn}{T})^2) $ памяти.
On Graph Problems in a Semi-Streaming Model, Feigenbaum, Kannan, McGregor, Suri, Zhang (там есть 5.83-приближение для паросочетания и многое другое)
A Data Structure for Dynamic Trees, Sleator, Tarjan, 1982
Динамические деревья на русском http://www.youtube.com/watch?v=GgHMmFUWtjo
8. Лекция 8. Полупотоковые алгоритмы на графах. Эскизы, разрезы, спарсификаторы
(23.11.2014 - 11:15 - 12:50)

Спарсификаторы. Построение в полупотоковом режиме за $ \tilde{O}(\varepsilon^{-2} n) $. Набросок построения в режиме offline. Эскиз графа через матрицу инциндентности. $ l_0 $-сэмплирование. Поиск компонент связности через эскизы, k-связность и поиск минимального разреза.

Спарсификаторы offline за $ \tilde{O}(\varepsilon^{-2}n) $, Nicholas Harvey + ссылка на курс CPSC 536N
Data Streams & Communication Complexity, McGregor, Amherst (про эскизы графов, разрезы и k-связность)
On Unifying the Space of $ l_0 $-Sampling Algorithms, Cormode, Firmani http://www.youtube.com/watch?v=E2WF7RLIPXo
Ваша оценка: Пусто Средняя: 4 (9 votes)
Share |