Хэши фильтра Блума: больше или больше?

15

При реализации фильтра Блума традиционный подход требует нескольких независимых хеш-функций. Кирш и Митценмахер показали, что на самом деле вам нужно только два, а остальные можно сгенерировать как линейные комбинации.

Мой вопрос: в чем на самом деле разница между двумя хэш-функциями и одной с двойной энтропией?

Это происходит из-за того, что вы на самом деле делаете с выводом ваших хеш-функций: вы берете свое (скажем) 64-битное хеш-значение и масштабируете его до размера вашего битового вектора, который, вероятно, значительно меньше 2 64 . Это явно преобразование с потерей энтропии (за исключением редкого случая, когда размер хеша и емкость фильтра точно совпадают). Предполагая, что мой фильтр содержит менее 2 32 записей, что может помешать мне разбить мое 64-битное значение хеша на два 32-битных хеша и принять их линейные комбинации? Или использовать его для посева PRNG?

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

Похоже, что я могу обойтись без битов для размера фильтра m или эквивалентно 2 ( lg ( - n ln p ) - 2 lg ( ln 2 ) ) битов, чтобы хранить n элементов с ложной положительной вероятностью р ....2Л.Г.(м)м2(Л.Г.(-Nперп)-2Л.Г.(пер2))Nп

Джей Хакер
источник

Ответы:

16

Вы правы, рассматривая хеш-функции в терминах «произведенных случайных битов». Поэтому, если у вас есть хеш-функция, которая создает 64-битный хеш, вы можете рассматривать как 4 16-битных хеша (путем разделения) и так далее.

2Л.Г.(м)

Михаил Мтизенмахер
источник
5
Добро пожаловать в историю, Майкл :)
Суреш Венкат