Smooth histograms for sliding window [Влад Бидзиля]

Описание

Пусть для построения приближения функции f в streaming модели имеется алгоритм A. Для случая, когда f удовлетворяет определенным условиям гладкости, будет показано, как адаптировать алгоритм A для построения приближения функции f в sliding window модели с полилогарифмическим (по длине потока) мультипликативным оверхедом по памяти и времени.


Данная техника адаптации была кратко описана в статье "Smooth histograms for sliding window - Vladimir Braverman, Rafail Ostrovsky" 2007 года и подробно изложена в статье "Effective computations on sliding windows - Vladimir Braverman, Rafail Ostrovsky" 2010 года.

Результат является более общим и сильным, чем предыдущая новаторская работа в данном направлении "Maintaining stream statistics over sliding windows - Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani" 2001 года.

Также на занятии будет продемонстрировано применение данной техники к ряду стандартных задач.