Фильтр Блума

Фильтр Блума (Bloom filter) — это вероятностная структура данных, придуманная Бертоном Блумом в 1970 году, позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.

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

Фильтр Блума представляет собой битовый массив из m бит. Изначально, когда структура данных хранит пустое множество, все m бит обнулены. Пользователь должен определить k независимых хеш-функций h1, …, hk, отображающих каждый элемент в одну из m позиций битового массива достаточно равномерным образом.

Для добавления элемента e необходимо записать единицы на каждую из позиций h1(e), …, hk(e) битового массива.

Для проверки принадлежности элемента e к множеству хранимых элементов, необходимо проверить состояние битов h1(e), …, hk(e). Если хотя бы один из них равен нулю, элемент не может принадлежать множеству (иначе бы при его добавлении все эти биты были установлены). Если все они равны единице, то структура данных сообщает, что е принадлежит множеству. При этом может возникнуть две ситуации: либо элемент действительно принадлежит множеству, либо все эти биты оказались установлены по случайности при добавлении других элементов, что и является источником ложных срабатываний в этой структуре данных.

Фильтр Блума с m = 9 и k = 3, хранящий множество из элементов A и B. Этот фильтр Блума может определить, что элемент C входит в множество, хотя он и не добавлен в него.

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

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

Свойства

  • В отличие от многих других структур данных (например, хеш-таблиц), также хранящих множество элементов, фильтр Блума может представлять универсальное множество всех возможных элементов. В этом случае все биты в его битовом массиве равны единице.
  • Объединение и пересечение двух фильтров Блума одинакового размера и c одинаковым множеством хеш-функций может быть реализовано побитовыми операциями OR и AND над их битовыми массивами.

Применение

По сравнению с хеш-таблицами, фильтр Блума может обходиться на несколько порядков меньшими объёмами памяти, жертвуя детерминизмом. Обычно он используется для уменьшения числа запросов к несуществующим данным в структуре данных с более дорогостоящим доступом (например, расположенной на жестком диске или в сетевой базе данных), то есть для «фильтрации» запросов к ней.

Примеры практических применений:

  • Прокси-сервер Squid использует фильтры Блума для опции cache digests. 
  • Google BigTable использует фильтры Блума для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных (Также его используют в Cassandra и LevelDB).
  • Компьютерные программы для проверки орфографии.
  • Bitcoin использует фильтр Блума, чтобы ускорить синхронизацию с кошельком.

 

Тэги: алгоритмы базы данных


 


 
архив

подписка