Почему эскиз Count-Min требует парных независимых хэш-функций?

Question

А Счет-мин эскиз это потрясающая структура данных для оценки частот различных элементов в потоке данных. Интуитивно, он работает, выбирая различные хэш -функции, хэшировал каждый элемент с этими хэш -функциями и увеличивая частоты различных слотов в различных таблицах. Чтобы оценить частоту элемента, эскиз Count-Min применяет хеш-функции к этим элементам и выводит минимальное значение из всех слотов, которые хешируются.

А Оригинальная бумага на эскизе графа-мин упоминает, что структура данных требует парных независимых хеш -функций, чтобы получить необходимые гарантии на ожидаемую производительность. Однако, глядя через структуру, я не понимаю, почему парная независимость необходима. Интуитивно, я бы подумал, что все, что потребуется, будет, чтобы функция хэш была универсальная хэш -функция, поскольку универсальные хеш -функции являются хэш -функциями с низкими вероятностями столкновений. Анализ вероятностей столкновения в эскизе графства-мин удивительно похож на анализ вероятностей столкновения в цепной хэш-таблице (который требует только семейства универсальных хэш-функций, а не парных независимых хеш-функций), и я не могу заметить разница в анализе.

Почему необходимо для хэш-функций в эскизе Count-Min быть парным независимым?

Спасибо!

Answer 1

Вы правы: универсального хеширования достаточно. Парная независимость, хотя и сильнее, является обычным методом построения универсальной семейства хэш. Также парная независимость контрастирует в статье с 4-миной независимостью, требуемой предыдущими методами, такими как эскиз AMS.