City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Streaming algorithms
Kazan / spring 2016, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

Источники.

  • 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.