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

Минимальные хэш-функции. Синхронизация множеств
Алгоритмы обработки потоковых данных


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

Описание

Сравнение множеств на равенство за \(O(\log\frac{1}{\delta} \log n)\) памяти. Семейство минимально независимых хэш-функций. Оценка символа Жаккара. Поиск числа редких элементов. Задача согласования множеств c ограниченной симметрической разностью \(O(k \log n)\).

A Small Approximately Min-Wise Independent Family of Hash Functions, Indyk, 2001

Set Reconciliation with Nearly Optimal Communication Complexity, Minsky, Trachtenberg, Zippel, 2004

Видео

Материалы