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

Минимальные хэш-функции. Синхронизация множеств
Streaming algorithms

What: Lecture
When: Sunday, 16 November 2014, 11:15–12:50
Where: ПОМИ РАН
Slides: streaming_algorithms_lecture_161114.pdf

Description

Сравнение множеств на равенство за \(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

Video