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

Детерминированный приближенный поиск статистик
Алгоритмы обработки потоковых данных


Что: Лекция
Когда: Воскресенье, 12 октября 2014, 11:15–12:50
Где: ПОМИ РАН

Описание

Алгоритм Гринвалда-Кханна находит приближенный в отношении статистики ответ с точностью \(\pm \epsilon \cdot m\), при этом использует памяти всего \(O(\frac{1}{\epsilon} \cdot \log(\epsilon \cdot m))\).
Статья Гринвалда-Кханна (2001)