В чем преимущество использования фильтров Блума?

Question

Я читаю на фильтрах Блума, и они просто кажутся глупыми.Все, что вы можете сделать с помощью фильтра Блума, вы можете сделать в меньшем пространстве, более эффективно, используя одну хэш-функцию, а не несколько, или это то, что кажется.Зачем вам использовать фильтр Блума и чем он полезен?

Answer 1

Из Википедия :

Фильтры Блума имеют сильное пространственное преимущество перед другими структурами данных для представления наборов, таких как самобалансирующиеся двоичные деревья поиска, попытки, хеш-таблицыили простые массивы или связанные списки записей.Большинство из них требуют хранения, по крайней мере, самих элементов данных, что может потребовать в любом месте от небольшого числа битов для небольших целых чисел до произвольного числа битов, например для строк (попытки являются исключением, поскольку они могут совместно использовать память междуэлементы с одинаковыми префиксами).Связанные структуры влекут за собой дополнительное линейное пространство для указателей.Фильтр Блума с ошибкой 1% и оптимальным значением k, с другой стороны, требует только около 9,6 битов на элемент - независимо от размера элементов.Это преимущество отчасти связано с его компактностью, унаследованной от массивов, и частично с его вероятностным характером.Если 1% ложных срабатываний кажется слишком высоким, каждый раз, когда мы добавляем около 4,8 бит на элемент, мы уменьшаем его в десять раз.

Довольно ясно для меня.

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

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

Так что пример использования шаблона может быть:

У вас на диске много данных - вы решаете, какую погрешность вы хотите (например, 1%), которая предписывает значение m .Затем определяется оптимальный k (по формуле, приведенной в статье).Вы заполняете свой фильтр из этих привязанных к диску данных один раз.

Теперь у вас есть фильтр в оперативной памяти.Когда вам нужно обработать какой-либо элемент, вы запрашиваете фильтр, чтобы узнать, есть ли у него шанс на существование в вашем наборе данных.Если этого не произойдет, дополнительная работа не выполняется.Нет чтения с диска и т. Д. (Что бы вам пришлось сделать, если бы это был хеш или дерево и т. Д.).

В противном случае, если фильтр говорит: «Да, он там», есть вероятность 1%, чтоэто неправильно, поэтому вы делаете необходимую работу, чтобы выяснить это.В 99% случаев это действительно будет , так что работа была не напрасной.

Answer 2

Алекс объяснил это довольно хорошо.Для тех, кто до сих пор не разбирался в этом, надеюсь, этот пример поможет вам понять:

Допустим, я работаю на Google, в команде Chrome, и хочу добавить в браузер функцию, котораяуведомляет пользователя, если введенный им URL является вредоносным URL.Итак, у меня есть набор данных из примерно 1 миллиона вредоносных URL-адресов, размер этого файла составляет около 25 МБ.Поскольку размер довольно большой (большой по сравнению с размером самого браузера), я храню эти данные на удаленном сервере.

Случай 1: Я использую хеш-функцию с хеш-таблицей.Я выбираю эффективную функцию хеширования и запускаю все 1 миллион URL-адресов через функцию хеширования, чтобы получить хеш-ключи.Затем я создаю хеш-таблицу (массив), где ключ хеша даст мне индекс для размещения этого URL.Итак, теперь, когда я хэшировал и заполнял хеш-таблицу, я проверял ее размер.Я сохранил все 1 миллион URL-адресов в хэш-таблице вместе с их ключами.Таким образом, размер не менее 25 МБ.Эта хеш-таблица, благодаря своему размеру, будет храниться на удаленном сервере.Когда пользователь приходит и вводит URL-адрес в адресную строку, мне нужно проверить, не является ли он вредоносным.Таким образом, я запускаю URL через хеш-функцию (сам браузер может сделать это), и я получаю хеш-ключ для этого URL.Теперь мне нужно сделать запрос к моему удаленному серверу с этим хеш-ключом, чтобы проверить, совпадает ли конкретный URL-адрес в моей хеш-таблице с этим конкретным ключом с тем, что ввел пользователь.Если да, то это вредоносно, а если нет, то не является вредоносным.Таким образом, каждый раз, когда пользователь вводит URL-адрес, необходимо выполнить запрос к удаленному серверу, чтобы проверить, является ли он вредоносным URL-адресом.Это займет много времени и, следовательно, замедлит работу моего браузера.

Случай 2: Я использую фильтр Блума.Весь список из 1 миллиона URL-адресов проходит через фильтр Блума с использованием нескольких хэш-функций, и соответствующие позиции помечаются как 1 в огромном массиве 0.Допустим, мы хотим получить ложно-положительную ставку 1%, используя калькулятор фильтра Блума (http://hur.st/bloomfilter?n=1000000&p=0.01), мы получаем требуемый размер фильтра Блума всего лишь 1,13 МБ. Ожидается, что этот небольшой размер, хотя и размермассива огромен, мы храним только 1 или 0, а не URL-адреса, как в случае хеш-таблицы. Этот массив можно рассматривать как битовый массив. То есть, поскольку у нас есть только два значения 1 и 0, мы можемустановите отдельные биты вместо байтов. Это уменьшит занимаемое пространство в 8 раз. Этот блум-фильтр размером 1,13 МБ из-за своего небольшого размера может храниться в самом веб-браузере !! Таким образом, когда пользователь приходит и вводит URL,мы просто применяем требуемые хеш-функции (в самом браузере) и проверяем все позиции в фильтре Блума (который хранится в браузере). Значение 0 в любой из позиций говорит нам, что этот URL НЕ ОПРЕДЕЛЕННОсписок вредоносных URL-адресов и пользователь могут свободно перемещаться. Таким образом, мы не звонили на сервер и, следовательно, сэкономили время. Значение 1 телНам нужно, чтобы URL мог быть в списке вредоносных URL.В этих случаях мы делаем вызов на удаленный сервер, и там мы можем использовать некоторую другую хеш-функцию с некоторой хеш-таблицей, как в первом случае, чтобы получить и проверить, присутствует ли URL-адрес.Поскольку в большинстве случаев URL-адрес вряд ли является вредоносным, небольшой фильтр Bloom в браузере обнаруживает это и, следовательно, экономит время, избегая обращений к удаленному серверу.Только в некоторых случаях, если фильтр Блума сообщает нам, что URL МОЖЕТ быть вредоносным, только в тех случаях мы делаем вызов на сервер.Это «могущество» на 99% верно.

Таким образом, используя небольшой фильтр Блума в браузере, мы сэкономили много времени, поскольку нам не нужно совершать серверные вызовы для каждого введенного URL-адреса.

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

edit :

Я внедрил фильтр Блума для задачи злонамеренного тестирования URL в Python. Код можно найти здесь - https://github.com/tarunsharma1/Bloom-Filter Код очень прост для понимания, подробное описание приведено в файле readme.

Answer 3

Я начну с объяснения того, что такое фильтр Блума, что он может и не может делать, зачем он нам нужен, покажу интуитивно понятное описание его работы, а затем приведу несколько примеров, когда они могут быть полезны.

Таким образом, стандартный фильтр Блума представляет собой вероятностную структуру данных , которую может ^*:

---

• добавить элемент в набор
• проверить, есть ли элемент в наборе, сообщив definitely not in the set или possibly in the set

Это possibly in the set, именно поэтому оно называется вероятностным. Использование умных слов означает, что возможно ложное срабатывание (возможны случаи, когда ложно считается, что элемент является положительным), но ложное отрицание невозможно.

Но это не может ^*:

• удалить предмет из набора
• даст вам список всех элементов, которые в настоящее время находятся в вашем наборе

^* _{Этот набор может / не может для базового фильтра Блума. Поскольку эта полезная структура данных была создана давно, люди нашли, как увеличить ее с помощью других полезных функций.}

---

Но подождите минуту: мы уже знаем структуру данных, которая может ответить на все это без смутного «возможного», а также без всех ограничений (не может удалить, не может показать все). И это называется set . А вот и главное преимущество фильтра Блума: он экономит пространство и постоянен .

Это означает, что не имеет значения, сколько элементов мы храним там, пространство будет одинаковым. Да, фильтр Блума с элементами 10^6 (бесполезный фильтр Блума) займет столько же места, сколько фильтр Блума с элементами 10^20 и то же пространство, что и фильтр Блума с элементами 0. Так сколько места это займет? Вы должны решить (но есть торговля: чем больше элементов у вас есть, тем больше вы неуверенны с вами possible in the set ответ.

Еще одна крутая вещь - это постоянная пространства. Когда вы сохраняете данные в набор, вы должны фактически сохранить эти данные. Поэтому, если вы храните this long string in the set, вам нужно использовать как минимум 27 байт. Но для ошибки в 1% и оптимального значения k ^** вам потребуется ~ 9,6 бит (<2 байта) на каждый элемент (будь то короткий тип int или огромная стена текста). </p>

Другим свойством является то, что все операции занимают постоянное время, которое абсолютно не совпадает с амортизированным постоянным временем в случае наборов (помните, что если набор имеет столкновения, он может ухудшиться со временем O(n)).

^** _{k - значение хеш-функций, используемых в фильтре Блума}

---

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

• вы инициируете пустой битовый массив длиной m
• Вы выбираете k различных хеш-функций (чем более независимы, тем лучше)
• если вы хотите добавить элемент, вы вычисляете все хэши k этого значения и устанавливаете соответствующие биты в 1
• Если вы хотите проверить, существует ли элемент, вы также вычисляете все хеши k, и если хотя бы один из них не задан, его, безусловно, нет в наборе. В противном случае это может быть в наборе.

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

---

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

Вот список более конкретных описаний:

• стандартный пример вредоносных веб-сайтов и браузера описан практически в любом месте , где люди говорят о фильтрах Блума
• является слабым паролем: вместо огромного набора всевозможных слабых паролей, вы можете просто проверить, не является ли пароль, несомненно, слабым, с помощью фильтра Bloom значительно меньшего размера
• если у вас есть список статей и список пользователей, вы можете использовать фильтр Блума, чтобы показать статьи пользователей, которые они не читали. Интересно, что у вас может быть только один фильтр (вы проверяете, есть ли комбинация user_id + article_id)
• биткойн использует фильтр Блума для синхронизации кошелька
• Веб-серверы Akamai используют фильтры Bloom для предотвращения сохранения «однократных чудес» в дисковых кешах. Чудеса одного удара - это веб-объекты, запрошенные пользователями только один раз, что, по мнению Акамаи, применимо почти к трем четвертям их инфраструктуры кэширования. Использование фильтра Блума для обнаружения второго запроса на веб-объект и кэширование этого объекта только по его второму запросу предотвращает попадание чудес в один удар в кэш-память диска, значительно снижая нагрузку на диск и увеличивая частоту обращений к кэш-памяти диска (взят из примеров в фильтре Блума статья в вики)

Answer 4

Фильтры Блума весьма полезны в биоинформатике.Они могут быть более компактными по сравнению с использованием обычного хэша, особенно когда размер строк, с которыми вы работаете, может составлять сотни миллионов букв с очень маленьким алфавитом, то есть {A, G, T, C}.Они обычно используются для оценки наличия или отсутствия определенного геномера в геноме.Вот пример того, что используется для чего-то уместного здесь .

РЕДАКТИРОВАТЬ:

Несколько хеш-функций используются для минимизации ложных срабатываний.Есть надежда, что между всеми k-хэш-функциями каждое значение будет иметь уникальную сигнатуру в битовом массиве по сравнению с любым другим возможным значением.Тем не менее, ложные срабатывания существуют, но их можно минимизировать до приемлемого уровня.Используя эту технику, вы хэшируете элементы независимо их размера.Когда вы ищете их, вы используете каждую хэш-функцию и проверяете, чтобы все их битовые значения были равны 1.

Сравните это с геномом человека, где увеличение размера элемента увеличивает размерсущественно хеш-таблица (размер таблицы 4 * 4 ^k ).Это предполагает, что вы кодируете элементы, используя 2 бита / букву.

Answer 5

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