вторник, июля 27, 2010

Фильтр Блума

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

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

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

Пример использования из Википедии:
Google BigTable использует фильтры Блума для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных.

(Пост опубликован в рамках недели борьбы с велосипедизмом)

20 коммент.:

Alex Ott комментирует...

Кстати, вот этот блог может быть достаточно интересен - человек часто пишет про основы нагруженных систем, поисковых систем и т.п.

Анонимный комментирует...

На самом деле довольно много очаровательных своей простотой решений основаны на допущении ложных срабатываний. Тот же самый алгоритм Рабина-Карпа поиска подстроки.

Самому подобное в нужный момент придумать никогда не удавалось...

Alexander комментирует...

Алёна, спасибо за ваш очень познавательный блог! Обычно описания алгоритмов скатываются в УГ. У вас их читать интересно. Ждём оставшиеся части велосипеда!

Анонимный комментирует...

Прикольно, не знал.

Правда непонятно как такие хэши генерировать.
Для hashmap достаточно шоб у разных элементов были разные хэши, а тут нужно много равновероятно установленных значащих бит.

P.S. Это soonts. OpenID опять не работает у тебя. Это уже далеко не в первый раз. Или пинай тех.поддержку google, или мигрируй нафик.

Alena комментирует...

soonts
Правда непонятно как такие хэши генерировать.
Для hashmap достаточно шоб у разных элементов были разные хэши, а тут нужно много равновероятно установленных значащих бит.


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

P.S. Это soonts. OpenID опять не работает у тебя. Это уже далеко не в первый раз. Или пинай тех.поддержку google,

Их постоянно пинают. Это известная проблема, что у них OpenID отваливается.

или мигрируй нафик.

лучше вы к нам :-)

arsenmuk комментирует...

Алена, спасибо! А можно немножко разжевать для тех кто в танке? Совсем не ясно как должны выглядеть используемые в алгоритме хеш-функции.. Если размер массива m, а k - количество функций, правильно ли я понимаю, что i-ая функция осуществляет отображение в i-ый элемент массива? Если ответом на мой вопрос является что-то в духе "хеш-функция может быть какая угодно", что вполне естественно, то совсем непонятно каким, все-таки, условиям она должна соответствовать и какие ограничения на нее наложены. Ведь, если никаких условий не наложить, то можно и здесь очередной велосипед наворотить с квадратными колесами)) Может быть кто-нибудь может поделиться примером?

sin комментирует...

Предлагаю осветить еще консистентное хэширование (consistent hashing)

Ivan комментирует...

Интересный фильтр, интересно какова вероятность ошибки? може

Alex Ott комментирует...

2Ivan: в статье на википедии есть формулы оценки вероятности

dm3 комментирует...

Вот неплохая статья про блум фильтры с имплементацией на Scala: http://www.codecommit.com/blog/scala/bloom-filters-in-scala.

Alena комментирует...

Arsen

Алена, спасибо!

пожалуйста :-)

А можно немножко разжевать для тех кто в танке?

да без проблем

Совсем не ясно как должны выглядеть используемые в алгоритме хеш-функции..

В учебных материалах обычно приводят примеры хеш-функций типа таких: "значение хеш-функции от строки равно длине строки". Это плохая функция, но наглядная. Пример хеш-функции из реального мира: MurmurHash

Если размер массива m, а k - количество функций, правильно ли я понимаю, что i-ая функция осуществляет отображение в i-ый элемент массива?

Нет. Вот как на приведенной у меня картинке:
h1(x)=1
h2(x)=5
h3(x)=13

h1(y)=4
h2(y)=11
h3(y)=16

h1(z)=3
h2(z)=5
h3(z)=11

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

Про хеш-функции вообще есть в Википедии: Hash function

Вот советы по выбору хеш-функций для фильтра Блума: A Few Notes on Bloom Filters

Alena комментирует...

sin

Предлагаю осветить еще консистентное хэширование (consistent hashing)

Уже! Правда, не я. :-) Вот отличный обзор: http://www.jprogers.info/2009/11/consistent-hashing.html

_winnie комментирует...

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

Вставка в множество за время порядка n?

Alena комментирует...

_winnie

Вставка в множество за время порядка n?

Ненененене.
Время добавления элемента в фильтр Блума фиксировано и равно O(k), где k - количество хеш-функций. Более того, это все еще и параллелится хорошо.

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

_winnie комментирует...

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

Если совместить несколько хеш-функций и ссылки вместо битов, то получается что-то отдалённо похожее на кукушкин хеш. http://blog.gamedeff.com/?p=62

Анонимный комментирует...

Здравствуйте, а не знаете ли вы где найти реализацию фильтра на каком-либо языке?

Alena комментирует...

Здравствуйте, а не знаете ли вы где найти реализацию фильтра на каком-либо языке?

Вот, например: http://code.google.com/p/bloom/

Погуглите, их полно...

Peter A. Kurishev комментирует...

Пост в принципе правильный, в плане велосипедизма, но только практически не добавляет новой информации. Мне вот очень интересно получить максимально быструю реализацию фильтра Блума на Си (не C++). Есть претенденты на эту роль?

Анонимный комментирует...

Ал
ёна, вы скорее ПОРОЖДАЕТЕ велосипеды, чем боретесь с ними такими постами....

Unknown комментирует...

Алена, один комментарий, скорее интересный для хардкорных ораклоидов и вообще DBA-шников.

Тут в посте был пример, что фильтры блума используются в Google BigTable, - а вот тут по ссылке есть пример того, как используются они в Oracle Database.

http://antognini.ch/papers/BloomFilters20080620.pdf