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

Мультипроходный точный детерминированный поиск статистик
Streaming algorithms

What: Lecture
When: Sunday, 05 October 2014, 11:15–12:50
Where: ПОМИ РАН

Description

Мы рассмотрим задачу поиска порядковых статистик в потоке и разберем детерминированные алгоритмы. Алгоритм Мунро-Патерсона находит точный ответ, но использует несколько проходов. При разрешенных $p$ проходах алгоритм использует $O(m^{1 \slash p} \log^{2 - 2 \slash p} m \log n)$ памяти.


Статья Мунро-Патерсона (1980)

Video