- PVSM.RU - https://www.pvsm.ru -
Фильтр Блума — это рандомизированная структура данных для запросов, разработанная Бёртоном Блумом в 1970 году. Фильтр Блума даёт ошибочный ответ на запрос, т.н. ложно-положитеное срабатывание. Т.е. если мы добавляем некоторый элемент, то существует отличная от нуля вероятность, что фильтр Блума вернет ответ что элемент находится в векторе, хотя его там нет.
Грубо говоря, фильтр Блума возвращает 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 это .
Объединяем эти формулы:
В итоге получается, что вероятность ложно-положительных срабатываний фильтра Блума из 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/
Нажмите здесь для печати.