Город: Санкт-Петербург Казань Язык: Русский English

Modern algorithms for parallel, streaming and query-based data processing
Санкт-Петербург / весна 2017, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

In this mini-course we will cover recent developments in approximate algorithms for processing very large data sets. We will focus on fundamental techniques that can be used in a variety of different computational settings, including MapReduce-like batch parallel computation, algorithms for streaming data and data that can be accessed through queries. The list of topics will include: — Linear sketching: a powerful paradigm for compressing data that is based on carefully chosen random linear projections. Linear sketching allows to construct approximate arrays, estimate the size of cuts in graphs, compute approximate matchings, reduce dimension of vectors, solve linear regression and other linear-algebraic problems, etc.

— Core-sets: a baseline approach to problems involving geometric data core-sets allow to solve a variety of clustering and related problems. Core-sets are constructed by representing a dataset as a carefully selected subset of its points.

— Beyond linear sketches and core-sets: we will see how to design algorithms for massive data processing in situations when linear sketches and core-sets fall short of achieving optimal performance.

— Query-based sampling methods: we will see how queries can be used to design approximate decision-making algorithms for testing properties of high-dimensional and noisy data.

Дата и время Название Место Материалы
03 июня
Лекция 1, лекция ПОМИ РАН слайдывидео
03 июня
Лекция 2, лекция ПОМИ РАН видео
04 июня
Лекция 3, лекция ПОМИ РАН слайдывидео
04 июня
Лекция 4, лекция ПОМИ РАН слайдывидео