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 года. Также на занятии будет продемонстрировано применение данной техники к ряду стандартных задач.

Видео Smooth histograms for sliding window [Влад Бидзиля] автора Кодовые Загадки