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

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


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

Описание

Введение. Кассовая и турникетная модели. Рассмотрим задачу поиска частых элементов. Дано $k$ и последовательность из $m$ чисел. Мы построим двух-проходный алгоритм (Мисра-Граеса), который находит все элементы, встречающиеся в последовательности хотя бы $\lfloor \frac{m}{k} \rfloor + 1$ раз, и использует $O(k(\log m + \log n))$ памяти. Также покажем нижнюю линейную оценку на память для одно-проходной версии задачи.


Статья Мисра-Граеса (1982)

Приложенные файлы