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

Streaming algorithms
Saint Petersburg / autumn 2014, посмотреть все семестры

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

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

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

Литература

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

Правила получения зачёта: rules.pdf