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

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

Источники.

• Mining of Massive Datasets, Ulman. Очень доходчивая и интересная книжка, есть глава про streaming.

• Data Streams: Algorithms and Applications, Muthukrishnan. Статья, переросшая в книгу. Хороший обзор.

• http://research.neustar.biz/ -- блог компании Neustar. Есть много интересных и подробных статей про streaming.

• http://www.cs.dartmouth.edu/~ac/Teach/CS49-Fall11/ -- курс Амита Чакрабарти в Дартмуте.

• http://grigory.us/big-data-class.html -- курс Григория Ярославцева по Big Data.