Почему фильтры Блума используют один и тот же массив для всех k алгоритмов хэширования

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

Не было бы более выгодно использовать k массивов, по одному для каждого алгоритма хеширования, так что, если по совпадению многие входные ключи сопоставляются алгоритмом A с одним и тем же значением и хранятся в одной и той же ячейке массива, а затем другой ключ сопоставляется алгоритмом B к тому же значению - это ценная информация, которую следует пометить отдельно. Я думаю, что k массивов размера m/k должны давать лучший результат, чем один массив размера m. Я ошибся?


algorithm bloom-filter
person akiva    schedule 06.03.2018    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Если предположить, что k << m, это не имеет значения.

Независимо от того, используем ли мы один массив размером m или k массивов размером m/k, один бит для элемента, хранящегося в фильтре, будет сталкиваться в среднем k/m раз с другим элементом, хранящимся в том же фильтре. Поскольку эти отдельные попарные столкновения по существу независимы, количество столкновений каждого бита с другими объектами подчиняется одному и тому же распределению Пуассона, и, следовательно, вероятность столкновения одинакова и, следовательно, вероятность столкновения каждого бита одинакова, и, следовательно, вероятность столкновения каждого бита одинакова. вероятность ложного срабатывания одинакова.

Поэтому все дело в простоте реализации.

person btilly    schedule 06.03.2018
comment
@MooingDuck Использование памяти для массива размером m такое же, как для k массивов размером m/k. :-) - person btilly; 07.03.2018
comment
Однако удивительным фактом является то, что если H и K являются двумя независимыми хорошими хеш-функциями, а K никогда не производит 0, то вы можете сделать свои k функциями H(x), H(x) + K(x), ..., H(x) + (k-1)K(x) (все операции мод m), и фильтр Блума, вероятно, работать хорошо. Это может значительно повысить производительность, потому что вычисление хороших хэш-функций намного дороже, чем арифметика. - person btilly; 07.03.2018
comment
Но имеет значение, если алгоритмы распределены неравномерно. В этом случае значение с большим количеством коллизий для алгоритма A отличается от такого коллизии для алгоритма B. - person akiva; 07.03.2018
comment
@akiva Если у вас есть структура данных, основанная на хеше, и у вас есть хеш, который не работает, значит, хеш-структура работает плохо. Это ожидаемо. - person btilly; 07.03.2018
comment
но вся идея нескольких хэшей предназначена для неработающих алгоритмов хеширования. В противном случае достаточно одного - person akiva; 07.03.2018
comment
@akiva Знаете ли вы, что такое en.wikipedia.org/wiki/Bloom_filter? Это тема для обсуждения, и одной хэш-функции недостаточно по причинам, которые не имеют ничего общего с неправильной работой хеш-функций. Другим примером структуры данных на основе хэша, для которой требуется несколько хэш-функций, является en.wikipedia.org/wiki/ Cuckoo_hashing. - person btilly; 07.03.2018