Фильтр Блума - это структура данных, придуманная Бёртоном Блумом в 1970 году, которая позволяет быстро проверять принадлежность элемента множеству, при этом не затратная по памяти.
Фильтр Блума представляет собой битовый массив, в которой с помощью нескольких хэш-функций отображается каждый элемент. Картинка из Википедии.
Фильтр Блума может сработать ложно. То есть элемента во множестве нет, а он говорит, что есть. И чем больше элементов в множестве, тем выше вероятность ложного срабатывания. Однако, если вы знаете, что основной массы элементов в вашем множестве нет, то этот фильтр очень удобен. Вы сначала прогоняете их все через фильтр. А потом проверяете еще раз каким-нибудь иным более точным образом.
Ложные срабатывания - не единственная проблема фильтра Блума. Еще из него нельзя удалять элементы. Есть различные расширения фильтра Блума, которые все-таки позволяют это делать, но, понятное дело, не бесплатно.
Пример использования из Википедии:
Google BigTable использует фильтры Блума для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных.
(Пост опубликован в рамках недели борьбы с велосипедизмом)
вторник, июля 27, 2010
Фильтр Блума
Подписаться на:
Комментарии к сообщению (Atom)
Atom feed
20 коммент.:
Кстати, вот этот блог может быть достаточно интересен - человек часто пишет про основы нагруженных систем, поисковых систем и т.п.
На самом деле довольно много очаровательных своей простотой решений основаны на допущении ложных срабатываний. Тот же самый алгоритм Рабина-Карпа поиска подстроки.
Самому подобное в нужный момент придумать никогда не удавалось...
Алёна, спасибо за ваш очень познавательный блог! Обычно описания алгоритмов скатываются в УГ. У вас их читать интересно. Ждём оставшиеся части велосипеда!
Прикольно, не знал.
Правда непонятно как такие хэши генерировать.
Для hashmap достаточно шоб у разных элементов были разные хэши, а тут нужно много равновероятно установленных значащих бит.
P.S. Это soonts. OpenID опять не работает у тебя. Это уже далеко не в первый раз. Или пинай тех.поддержку google, или мигрируй нафик.
soonts
Правда непонятно как такие хэши генерировать.
Для hashmap достаточно шоб у разных элементов были разные хэши, а тут нужно много равновероятно установленных значащих бит.
В Википедии со странички фильтра Блума есть ссылки на какие-то эпичные труды по поводу выбора хэш-функций для него. Но я их не читала.
P.S. Это soonts. OpenID опять не работает у тебя. Это уже далеко не в первый раз. Или пинай тех.поддержку google,
Их постоянно пинают. Это известная проблема, что у них OpenID отваливается.
или мигрируй нафик.
лучше вы к нам :-)
Алена, спасибо! А можно немножко разжевать для тех кто в танке? Совсем не ясно как должны выглядеть используемые в алгоритме хеш-функции.. Если размер массива m, а k - количество функций, правильно ли я понимаю, что i-ая функция осуществляет отображение в i-ый элемент массива? Если ответом на мой вопрос является что-то в духе "хеш-функция может быть какая угодно", что вполне естественно, то совсем непонятно каким, все-таки, условиям она должна соответствовать и какие ограничения на нее наложены. Ведь, если никаких условий не наложить, то можно и здесь очередной велосипед наворотить с квадратными колесами)) Может быть кто-нибудь может поделиться примером?
Предлагаю осветить еще консистентное хэширование (consistent hashing)
Интересный фильтр, интересно какова вероятность ошибки? може
2Ivan: в статье на википедии есть формулы оценки вероятности
Вот неплохая статья про блум фильтры с имплементацией на Scala: http://www.codecommit.com/blog/scala/bloom-filters-in-scala.
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
sin
Предлагаю осветить еще консистентное хэширование (consistent hashing)
Уже! Правда, не я. :-) Вот отличный обзор: http://www.jprogers.info/2009/11/consistent-hashing.html
Из ссылки на википедию:
Как следствие, заметим, что для того, чтобы фильтр Блума поддерживал заданную ограниченную вероятность ложного срабатывания, размер битового массива должен быть линейно-пропорционален числу вставленных элементов.
Вставка в множество за время порядка n?
_winnie
Вставка в множество за время порядка n?
Ненененене.
Время добавления элемента в фильтр Блума фиксировано и равно O(k), где k - количество хеш-функций. Более того, это все еще и параллелится хорошо.
То, что ты зацитировал, означает следующее. Ты должен примерно знать какое число элементов у тебя будет в фильтре и выбирать размер фильтра исходя из этой величины.
А если в битовом массиве хранить вместо булевского флажка ссылку на интрузивный список с элементами, получаем обычную хеш-таблицу.
Если совместить несколько хеш-функций и ссылки вместо битов, то получается что-то отдалённо похожее на кукушкин хеш. http://blog.gamedeff.com/?p=62
Здравствуйте, а не знаете ли вы где найти реализацию фильтра на каком-либо языке?
Здравствуйте, а не знаете ли вы где найти реализацию фильтра на каком-либо языке?
Вот, например: http://code.google.com/p/bloom/
Погуглите, их полно...
Пост в принципе правильный, в плане велосипедизма, но только практически не добавляет новой информации. Мне вот очень интересно получить максимально быструю реализацию фильтра Блума на Си (не C++). Есть претенденты на эту роль?
Ал
ёна, вы скорее ПОРОЖДАЕТЕ велосипеды, чем боретесь с ними такими постами....
Алена, один комментарий, скорее интересный для хардкорных ораклоидов и вообще DBA-шников.
Тут в посте был пример, что фильтры блума используются в Google BigTable, - а вот тут по ссылке есть пример того, как используются они в Oracle Database.
http://antognini.ch/papers/BloomFilters20080620.pdf
Отправить комментарий