- PVSM.RU - https://www.pvsm.ru -

Количество ложно-положительных срабатываний фильтра Блума [перевод]

Количество ложно-положительных срабатываний фильтра Блума.

Описание

Фильтр Блума — это рандомизированная структура данных для запросов, разработанная Бёртоном Блумом в 1970 году. Фильтр Блума даёт ошибочный ответ на запрос, т.н. ложно-положитеное срабатывание. Т.е. если мы добавляем некоторый элемент, то существует отличная от нуля вероятность, что фильтр Блума вернет ответ что элемент находится в векторе, хотя его там нет.

Грубо говоря, фильтр Блума возвращает 2 возможных ответа:

  1. элемента нет в векторе
  2. элемент возможно есть в векторе

Блум проанализировал вероятность таких ошибочных ответов, но его анализ является некорректным.

В статье я не буду описывать построение фильтра Блума, об этом можно прочитать в соответствующей статье Фильтр Блума [1] или на вики WIKI: Фильтр Блума [2]

Введение

Фильтр Блума представляет собой структуру данных, которая отображает множество S из n элементов в битовый вектор Количество ложно положительных срабатываний фильтра Блума [перевод]. Для записи элемента используются k-случайных хэш-функций, таких что Количество ложно положительных срабатываний фильтра Блума [перевод]. Изначально вектор инициализируется нулями. Запись элемента производится путем установки в единицу всех k-бит в векторе B, т.е. Количество ложно положительных срабатываний фильтра Блума [перевод]. Для проверки существования элемента Количество ложно положительных срабатываний фильтра Блума [перевод] в фильтре достаточно узнать значения каждого k-бита вектора. Если есть хотя бы один ноль, то это значит что такого элемента ещё в векторе нет, а если все биты установлены в единицу, это говорит о том, что элемент вероятно уже существует. Эта ситуация называется ложно-положительным срабатыванием.

Блум посчитал ложно-положительные срабатывания следующим образом:
Вероятность, что любой бит вектора B равен нулю — это Количество ложно положительных срабатываний фильтра Блума [перевод] после установки всех единиц k-хэш-функций при добавлении n-элементов.
По этому, вероятность что конкретный бит будет установлен в единицу это

Количество ложно положительных срабатываний фильтра Блума [перевод]

Теперь, что бы привести Количество ложно положительных срабатываний фильтра Блума [перевод] к ложно-положительным срабатываниям, каждый из k-битов вектора Количество ложно положительных срабатываний фильтра Блума [перевод] должен быть установлен в единицу. Вероятность этого:

Количество ложно положительных срабатываний фильтра Блума [перевод]

которая, как утверждается равна

Количество ложно положительных срабатываний фильтра Блума [перевод]

Это доказательство, которое появилось много лет назад некорректное. Ошибка кроется в том, что делается неявное предположение, что событие Количество ложно положительных срабатываний фильтра Блума [перевод] и событие Количество ложно положительных срабатываний фильтра Блума [перевод] считаются независимыми. На первый взгляд это похоже на правду, так как Количество ложно положительных срабатываний фильтра Блума [перевод] независимы. Однако, простой контрпример к доказательству может быть получен учитывая случай Количество ложно положительных срабатываний фильтра Блума [перевод]. В этом случае при простом перечисление 16 возможных ситуаций обнаруживается вероятность ложно-положительного срабатывания как 5/8, в то время как формула Блума даёт результат 9/16 = 4.5/8

Точная формула

Смоделируем проблему определения количества ложно-положительных срабатываний как проблему шаров и корзин. У нас есть m-корзин. Мы бросаем kn белых шаров в случайные корзины. Мы можем считать корзину белой, если она содержит хотя бы один белый шар. Дальше мы помещаем k-черных шаров в корзины. Пусть событие A состоит в том, что каждый черный шар расположен в белой корзине. Посчитаем вероятность этого события Количество ложно положительных срабатываний фильтра Блума [перевод].
Заметим что множество белый корзиночек может быть представлено как подмножество Количество ложно положительных срабатываний фильтра Блума [перевод]. Для любого Количество ложно положительных срабатываний фильтра Блума [перевод] Количество ложно положительных срабатываний фильтра Блума [перевод] обозначим Количество ложно положительных срабатываний фильтра Блума [перевод] как событие состоящее в том, что I — это множество белых корзин. Мощность I равна Количество ложно положительных срабатываний фильтра Блума [перевод]. Воспользуемся формулой условной вероятности:

Количество ложно положительных срабатываний фильтра Блума [перевод]

Если I фиксированно, то
Количество ложно положительных срабатываний фильтра Блума [перевод]
, где Количество ложно положительных срабатываний фильтра Блума [перевод] содержит в себе

  • количество отображений из множества размера kn во множество значений i и
  • количество функций из множества размера kn во множество размера m

Количество отображений из множества размера kn во множество размера i описывается формулой Количество ложно положительных срабатываний фильтра Блума [перевод], где
Количество ложно положительных срабатываний фильтра Блума [перевод]

Количество функций из множества размера kn во множество размера m это Количество ложно положительных срабатываний фильтра Блума [перевод].

Объединяем эти формулы:
Количество ложно положительных срабатываний фильтра Блума [перевод]

Итоговый результат

В итоге получается, что вероятность ложно-положительных срабатываний фильтра Блума из m бит при добавлении n элементов, используя k-хэш-функций равна:

Количество ложно положительных срабатываний фильтра Блума [перевод]

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

Количество ложно положительных срабатываний фильтра Блума [перевод]

Текст оригинальной статьи:
ON THE FALSE-POSITIVE RATE OF BLOOM FILTERS [3]

Автор: Xardas2000

Источник [4]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/matematika/44991

Ссылки в тексте:

[1] Фильтр Блума: http://habrahabr.ru/post/112069/

[2] WIKI: Фильтр Блума: https://ru.wikipedia.org/wiki/Фильтр_Блума

[3] ON THE FALSE-POSITIVE RATE OF BLOOM FILTERS : http://people.scs.carleton.ca/~kranakis//Papers/TR-07-07.pdf

[4] Источник: http://habrahabr.ru/post/196364/