Фильтр Блума

Блум фильтр является пространственно-эффективным вероятностной структурой данных , задумана Burton Говарда Блумом в 1970 году, который используется для тестирования является ли элемент является членом набора . Ложноположительные совпадения возможны, но ложноотрицательные нет - другими словами, запрос возвращает либо «возможно в наборе», либо «определенно не в наборе». Элементы могут быть добавлены в набор, но не удалены (хотя это можно решить с помощью варианта фильтра Блума с подсчетом ); чем больше добавлено элементов, тем больше вероятность ложных срабатываний.

Блум предложил метод для приложений, в которых объем исходных данных потребовал бы непрактично большого объема памяти, если бы применялись «обычные» безошибочные методы хеширования . Он привел пример алгоритма расстановки переносов для словаря из 500 000 слов, из которых 90% следуют простым правилам расстановки переносов, а оставшиеся 10% требуют дорогостоящего доступа к диску для получения определенных шаблонов расстановки переносов. С достаточной основной памятьюможно использовать безошибочный хэш, чтобы исключить все ненужные обращения к диску; с другой стороны, при ограниченной основной памяти метод Блума использует меньшую хэш-область, но все же устраняет большинство ненужных обращений. Например, хеш-область размером всего 15% от размера, необходимого для идеального безошибочного хеширования, по-прежнему исключает 85% обращений к диску. ^[1]

В более общем плане для 1% вероятности ложного срабатывания требуется менее 10 битов на элемент, независимо от размера или количества элементов в наборе. ^[2]

Описание алгоритма [ править ]

Пустой фильтр Блум является битовым массивом из м бит, все готово к 0. Там также должно быть K различного хеша - функции , определенная, каждый из которых MAPS или Хэш некоторых множества элементов к одному из м позиций массива, создавая равномерное случайное распределение. Обычно k представляет собой небольшую константу, которая зависит от желаемой частоты ложных ошибок ε , в то время как m пропорционально k и количеству добавляемых элементов.

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

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

Требование разработки k различных независимых хеш-функций может быть недопустимым для больших k . Для хорошей хеш-функции с широким выводом должна быть небольшая корреляция между разными битовыми полями такого хеш-кода, поэтому этот тип хеш-функции можно использовать для генерации нескольких "разных" хеш-функций путем разделения его вывода на несколько битов. поля. В качестве альтернативы можно передать k различных начальных значений (например, 0, 1, ..., k  - 1) в хэш-функцию, которая принимает начальное значение; или добавьте (или допишите) эти значения к ключу. Для больших m и / или k независимость хэш-функций может быть ослаблена с незначительным увеличением количества ложных срабатываний. ^[3](В частности, Диллинджер и Манолиос (2004b) демонстрируют эффективность получения индексов k с использованием улучшенного двойного или тройного хеширования , вариантов двойного хеширования , которые фактически представляют собой простые генераторы случайных чисел, засеянные двумя или тремя значениями хеширования.)

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

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

Часто бывает так, что все ключи доступны, но их перечисление дорого (например, требует много операций чтения с диска). Когда количество ложных срабатываний становится слишком высоким, фильтр можно регенерировать; это должно быть относительно редким событием.

Преимущества пространства и времени [ править ]

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

Однако, если количество потенциальных значений невелико и многие из них могут быть в наборе, фильтр Блума легко превзойти детерминированный битовый массив , который требует только один бит для каждого потенциального элемента. Хеш-таблицы получают преимущество в пространстве и времени, если они начинают игнорировать коллизии и сохраняют только то, содержит ли каждый сегмент запись; в данном случае они фактически превратились в фильтры Блума с k  = 1. ^[4]

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

Чтобы понять его эффективность использования пространства, поучительно сравнить общий фильтр Блума с его частным случаем, когда k  = 1. Если k = 1, то для того, чтобы поддерживать достаточно низкую частоту ложных срабатываний, следует установить небольшую долю битов, это означает, что массив должен быть очень большим и содержать длинные серии нулей. Информационное содержание массива относительно его размера является низким. Обобщенный фильтр Блума ( k больше 1) позволяет установить намного больше битов, сохраняя при этом низкую частоту ложных срабатываний; если параметры ( k и m ) выбраны правильно, примерно половина битов будет установлена, ^[5] и они будут явно случайными, что минимизирует избыточность и максимизирует информационное содержание.

Вероятность ложных срабатываний [ править ]

Вероятность ложного срабатывания как функция количества элементов в фильтре и размера фильтра . Предполагается оптимальное количество хеш-функций .${\ displaystyle p}$${\ displaystyle n}$${\ displaystyle m}$${\ Displaystyle к = (м / п) \ пер 2}$

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

${\ displaystyle 1 - {\ frac {1} {m}}.}$

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

${\ displaystyle \ left (1 - {\ frac {1} {m}} \ right) ^ {k}.}$

Мы можем использовать известное тождество для e ⁻¹

${\ displaystyle \ lim _ {m \ to \ infty} \ left (1 - {\ frac {1} {m}} \ right) ^ {m} = {\ frac {1} {e}}}$

сделать вывод , что при большом т ,

${\ displaystyle \ left (1 - {\ frac {1} {m}} \ right) ^ {k} = \ left (\ left (1 - {\ frac {1} {m}} \ right) ^ {m } \ right) ^ {k / m} \ приблизительно e ^ {- k / m}.}$

Если мы вставили n элементов, вероятность того, что определенный бит по-прежнему равен 0, равна

${\ displaystyle \ left (1 - {\ frac {1} {m}} \ right) ^ {kn} \ приблизительно e ^ {- kn / m};}$

вероятность того, что это 1, поэтому

${\ displaystyle 1- \ left (1 - {\ frac {1} {m}} \ right) ^ {kn} \ приблизительно 1-e ^ {- kn / m}.}$

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

${\displaystyle \varepsilon =\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}.}$

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

Альтернативный анализ, приводящий к тому же приближению без предположения о независимости, представлен Митценмахером и Упфалом. ^[6] После того, как все n элементов были добавлены в фильтр Блума, пусть q будет долей из m битов, которые установлены в 0. (То есть количество битов, все еще установленных в 0, равно qm .) принадлежность элемента не в наборе, для позиции массива, заданной любой из k хэш-функций, вероятность того, что бит будет найден установленным в 1, равна . Таким образом, вероятность того, что все k хеш-функций обнаружат, что их бит установлен в 1, равна . Далее, ожидаемое значение q${\displaystyle 1-q}$${\displaystyle (1-q)^{k}}$- это вероятность того, что данная позиция массива не будет затронута каждой из k хэш-функций для каждого из n элементов, что (как указано выше)

${\displaystyle E[q]=\left(1-{\frac {1}{m}}\right)^{kn}}$.

Без предположения независимости можно доказать, что q очень сильно сконцентрировано вокруг своего ожидаемого значения. В частности, из неравенства Адзумы – Хёффдинга они доказывают, что ^[7]

${\displaystyle \Pr(\left|q-E[q]\right|\geq {\frac {\lambda }{m}})\leq 2\exp(-2\lambda ^{2}/kn)}$

Из-за этого мы можем сказать, что точная вероятность ложных срабатываний равна

${\displaystyle \sum _{t}\Pr(q=t)(1-t)^{k}\approx (1-E[q])^{k}=\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}}$

как прежде.

Оптимальное количество хеш-функций [ править ]

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

${\displaystyle k={\frac {m}{n}}\ln 2.}$

Требуемое количество бит, m , с учетом n (количество вставленных элементов) и желаемой вероятности ложного срабатывания ε (и при условии, что используется оптимальное значение k ) может быть вычислено путем подстановки оптимального значения k в выражение вероятности выше :

${\displaystyle \varepsilon =\left(1-e^{-({\frac {m}{n}}\ln 2){\frac {n}{m}}}\right)^{{\frac {m}{n}}\ln 2}}$

который можно упростить до:

${\displaystyle \ln \varepsilon =-{\frac {m}{n}}\left(\ln 2\right)^{2}.}$

Это приводит к:

${\displaystyle m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}}}$

Таким образом, оптимальное количество бит на элемент

${\displaystyle {\frac {m}{n}}=-{\frac {\log _{2}\varepsilon }{\ln 2}}\approx -1.44\log _{2}\varepsilon }$

с соответствующим количеством хеш-функций k (без учета целостности):

${\displaystyle k=-{\frac {\ln \varepsilon }{\ln 2}}=-\log _{2}\varepsilon .}$

Это означает, что для данной вероятности ложного срабатывания ε длина фильтра Блума m пропорциональна количеству фильтруемых элементов n, а необходимое количество хеш-функций зависит только от целевой вероятности ложного срабатывания ε . ^[8]

Формула приблизительна по трем причинам. Во-первых, и это наименее опасно, оно приближается как , что является хорошим асимптотическим приближением (т. Е. Которое выполняется при m → ∞). Во-вторых, что вызывает большее беспокойство, он предполагает, что во время теста членства событие, когда один проверяемый бит установлен в 1, не зависит от события, когда любой другой тестируемый бит установлен в 1. В-третьих, что вызывает наибольшее беспокойство, предполагается, что это случайное целое. .${\displaystyle m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}}}$${\displaystyle 1-{\frac {1}{m}}}$${\displaystyle e^{-{\frac {1}{m}}}}$${\displaystyle k={\frac {m}{n}}\ln 2}$

Гоэль и Гупта ^[9], однако, дают строгую верхнюю оценку, которая не делает никаких приближений и не требует никаких предположений. Они показывают, что вероятность ложного срабатывания для конечного фильтра Блума с m битами ( ), n элементами и k хэш-функциями не превосходит${\displaystyle m>1}$

${\displaystyle \varepsilon \leq \left(1-e^{-{\frac {k(n+0.5)}{m-1}}}\right)^{k}.}$

Эту границу можно интерпретировать как указание на то, что приближенная формула может применяться со штрафом не более чем на половину дополнительного элемента и не более чем на один бит меньше.${\displaystyle \left(1-e^{-{\frac {kn}{m}}}\right)^{k}}$

Приблизительное количество элементов в фильтре Блума [ править ]

Swamidass & Baldi (2007) показали, что количество элементов в фильтре Блума можно приблизительно оценить по следующей формуле:

${\displaystyle n^{*}=-{\frac {m}{k}}\ln \left[1-{\frac {X}{m}}\right],}$

где - оценка количества элементов в фильтре, m - длина (размер) фильтра, k - количество хэш-функций, а X - количество битов, установленных на единицу.${\displaystyle n^{*}}$

Объединение и пересечение множеств [ править ]

Фильтры Блума - это способ компактного представления набора элементов. Обычно пытаются вычислить размер пересечения или объединения двух наборов. Фильтры Блума можно использовать для приблизительного определения размера пересечения и объединения двух наборов. Swamidass & Baldi (2007) показали, что для двух фильтров Блума длиной m их количество, соответственно, можно оценить как

${\displaystyle n(A^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A|}{m}}\right]}$

и

${\displaystyle n(B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|B|}{m}}\right].}$

Размер их союза можно оценить как

${\displaystyle n(A^{*}\cup B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A\cup B|}{m}}\right],}$

где - количество битов, равное единице в любом из двух фильтров Блума. Наконец, пересечение можно оценить как${\displaystyle n(A\cup B)}$

${\displaystyle n(A^{*}\cap B^{*})=n(A^{*})+n(B^{*})-n(A^{*}\cup B^{*}),}$

используя три формулы вместе.

Интересные свойства [ править ]

• В отличие от стандартной хеш-таблицы, использующей открытую адресацию для разрешения конфликтов , фильтр Блума фиксированного размера может представлять набор с произвольно большим количеством элементов; добавление элемента никогда не заканчивается неудачей из-за «заполнения» структуры данных. Однако частота ложных срабатываний постоянно увеличивается по мере добавления элементов до тех пор, пока все биты в фильтре не будут установлены в 1, после чего все запросы будут давать положительный результат. При хешировании с открытой адресацией ложные срабатывания никогда не возникают, но производительность постоянно ухудшается, пока поиск не приближается к линейному поиску.
• Объединение и пересечение фильтров Блума с одинаковым размером и набором хэш-функций может быть реализовано с помощью операций поразрядного ИЛИ и И соответственно. Операция объединения в фильтрах Блума без потерь в том смысле, что результирующий фильтр Блума такой же, как фильтр Блума, созданный с нуля с использованием объединения двух наборов. Операция пересечения удовлетворяет более слабому свойству: вероятность ложного срабатывания в результирующем фильтре Блума не более чем вероятность ложного срабатывания в одном из составляющих фильтров Блума, но может быть больше, чем вероятность ложного срабатывания в фильтре Блума, созданном с нуля с использованием пересечение двух наборов.
• Некоторые виды наложенного кода можно рассматривать как фильтр Блума, реализованный с помощью физических карт с надрезом . Примером может служить затокодирование , изобретенное Кэлвином Мурсом в 1947 году, в котором набор категорий, связанных с частью информации, представлен метками на карточке со случайным шаблоном из четырех меток для каждой категории.

Примеры [ править ]

• Плодовые мушки используют модифицированную версию фильтров Блума для обнаружения новизны запаха с дополнительными функциями, включая сходство нового запаха с запахом ранее испытанных образцов и время, прошедшее с момента предыдущего опыта того же запаха. ^[10]
• Серверы Akamai Technologies , поставщика услуг по доставке контента , используют фильтры Блума, чтобы предотвратить сохранение в его дисковых кэшах «одноразовых чудес». Одноразовые чудеса - это веб-объекты, запрошенные пользователями только один раз, что, как обнаружил Akamai, применимо почти к трем четвертям их инфраструктуры кэширования. Использование фильтра Блума для обнаружения второго запроса веб-объекта и кэширования этого объекта только при его втором запросе предотвращает попадание «чудес с одним попаданием» в дисковый кеш, что значительно снижает рабочую нагрузку на диск и увеличивает процент попаданий в дисковый кеш. ^[11]
• Google Bigtable , Apache HBase и Apache Cassandra и PostgreSQL ^[12] использовать Bloom фильтры для уменьшения диска просмотра для несуществующих строк или столбцов. Избежание дорогостоящего поиска на диске значительно увеличивает производительность операции запроса к базе данных. ^[13]
• Google Chrome веб - браузер , используемый использовать фильтр Блума для выявления вредоносной URL. Любой URL-адрес сначала проверялся на соответствие локальному фильтру Блума, и только в том случае, если фильтр Блума давал положительный результат, выполнялась полная проверка URL-адреса (и пользователь предупреждался, если это тоже вернуло положительный результат). ^{[14] [15]}
• Microsoft Bing (поисковая система) использует многоуровневые иерархические фильтры Блума для своего поискового индекса BitFunnel . Фильтры Блума обеспечивали более низкую стоимость, чем предыдущий индекс Bing, основанный на инвертированных файлах . ^[16]
• Squid Web Proxy Cache использует фильтры Блума для дайджестов кэша . ^[17]
• Биткойн использовал фильтры Блума для ускорения синхронизации кошелька, пока не были обнаружены уязвимости конфиденциальности с применением фильтров Блума. ^{[18] [19]}
• Система архивного хранения Venti использует фильтры Блума для обнаружения ранее сохраненных данных. ^[20]
• Средство проверки модели SPIN использует фильтры Блума для отслеживания достижимого пространства состояний для больших проблем проверки. ^[21]
• В Cascading АНАЛИТИКА структура использует Bloom фильтры для ускорения асимметричных соединений, где один из соединяемых наборов данных значительно больше , чем другие (часто называемого Bloom присоединиться к литературе по базам данных). ^[22]
• Exim агент пересылки почты (MTA) использует фильтры Блума в скорости предельной функции. ^[23]
• Medium использует фильтры Блума, чтобы не рекомендовать статьи, которые пользователь ранее читал. ^[24]
• Ethereum использует фильтры Блума для быстрого поиска журналов в блокчейне Ethereum.

Альтернативы [ править ]

Классические фильтры Блума используют биты пространства на вставленный ключ, где - частота ложных срабатываний фильтра Блума. Однако пространство, которое строго необходимо для любой структуры данных, играющей ту же роль, что и фильтр Блума, приходится только на ключ. ^[25] Следовательно, фильтры Блума используют на 44% больше места, чем эквивалентная оптимальная структура данных. Вместо этого Pagh et al. обеспечить оптимальную структуру данных. Более того, их структура данных имеет постоянную локальность ссылки независимо от частоты ложных срабатываний, в отличие от фильтров Блума, где более низкая частота ложных срабатываний приводит к большему количеству обращений к памяти на запрос,${\displaystyle 1.44\log _{2}(1/\varepsilon )}$${\displaystyle \varepsilon }$${\displaystyle \log _{2}(1/\varepsilon )}$${\displaystyle \varepsilon }$${\displaystyle \log(1/\varepsilon )}$. Кроме того, он позволяет удалять элементы без штрафа за место, в отличие от фильтров Блума. Те же улучшенные свойства оптимального использования пространства, постоянная местность ссылки, а также возможность удаления элементов, также предусмотрены кукушкой фильтром из вентилятора и др. (2014) , реализация которого доступна с открытым исходным кодом.

Стерн и Дилл (1996) описывают вероятностную структуру, основанную на хэш-таблицах , хэш- сжатии , которые Диллинджер и Манолиос (2004b) определяют как значительно более точные, чем фильтр Блума, когда каждый из них настроен оптимально. Диллинджер и Манолиос, однако, отмечают, что разумная точность любого заданного фильтра Блума в широком диапазоне количества добавлений делает его привлекательным для вероятностного перечисления пространств состояний неизвестного размера. Следовательно, сжатие хэша является привлекательным, когда количество добавлений можно точно спрогнозировать; однако, несмотря на то, что это очень быстрое программное обеспечение, сжатие хэшей плохо подходит для аппаратного обеспечения из-за наихудшего линейного времени доступа.

Путце, Сандерс и Синглер (2007) изучили некоторые варианты фильтров Блума, которые либо быстрее, либо занимают меньше места, чем классические фильтры Блума. Основная идея быстрого варианта состоит в том, чтобы поместить k значений хэша, связанных с каждым ключом, в один или два блока, имеющих тот же размер, что и блоки кэша памяти процессора (обычно 64 байта). Предположительно, это повысит производительность за счет уменьшения количества потенциальных промахов кеш- памяти . Однако недостатком предложенных вариантов является использование примерно на 32% больше места, чем у классических фильтров Блума.

Вариант с эффективным использованием пространства основан на использовании одной хэш-функции, которая генерирует для каждого ключа значение в диапазоне, где - запрошенная частота ложных срабатываний. Затем последовательность значений сортируется и сжимается с использованием кодирования Голомба (или какой-либо другой техники сжатия), чтобы занять пространство, близкое к${\displaystyle \left[0,n/\varepsilon \right]}$${\displaystyle \varepsilon }$${\displaystyle n\log _{2}(1/\varepsilon )}$биты. Чтобы запросить фильтр Блума для данного ключа, достаточно проверить, сохранено ли его соответствующее значение в фильтре Блума. Распаковка всего фильтра Блума для каждого запроса сделает этот вариант полностью непригодным для использования. Чтобы решить эту проблему, последовательность значений делится на небольшие блоки равного размера, которые сжимаются отдельно. Во время запроса в среднем нужно будет распаковать только половину блока. Из-за накладных расходов на декомпрессию этот вариант может быть медленнее, чем классические фильтры Блума, но это может быть компенсировано тем фактом, что необходимо вычислить одну хеш-функцию.

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

Graf & Lemire (2019) описывает подход, называемый фильтром xor, где они хранят отпечатки пальцев в определенном типе идеальной хеш- таблицы, создавая фильтр, который более эффективен с точки зрения памяти ( бит на ключ) и быстрее, чем фильтры Блума или кукушки. (Экономия времени достигается за счет того, что для поиска требуется ровно три доступа к памяти, которые могут выполняться параллельно.) Однако создание фильтра сложнее, чем фильтры Блума и кукушки, и невозможно изменить набор после создания.${\displaystyle 1.23\log _{2}(1/\varepsilon )}$

Расширения и приложения [ править ]

Существует более 60 вариантов фильтров Блума, множество обзоров в данной области и постоянный отток приложений (см., Например, Луо и др. ^[26] ). Некоторые из вариантов в значительной степени отличаются от исходного предложения, чтобы быть нарушением или развилкой исходной структуры данных и ее философии. ^[26] Еще предстоит провести обработку, объединяющую фильтры Блума с другими работами по случайным проекциям , компрессионному восприятию и хешированию, чувствительному к местности (хотя см. Dasgupta и др. ^[27] для одной попытки, вдохновленной нейробиологией).

Фильтрация кеша [ править ]

Сети доставки контента развертывают веб-кешипо всему миру, чтобы кэшировать и предоставлять пользователям веб-контент с большей производительностью и надежностью. Ключевым применением фильтров Блума является их использование для эффективного определения, какие веб-объекты хранить в этих веб-кэшах. Почти три четверти URL-адресов, к которым осуществляется доступ из типичного веб-кеша, представляют собой «чудеса одного обращения», к которым пользователи обращаются только один раз и никогда больше. Совершенно очевидно, что дисковые ресурсы хранить в веб-кеше одноразовые чудеса расточительно, поскольку к ним больше никогда не будет доступа. Чтобы предотвратить кеширование «чудеса одного удара», используется фильтр Блума для отслеживания всех URL-адресов, к которым обращаются пользователи. Веб-объект кэшируется только в том случае, если к нему обращались по крайней мере один раз, т. Е. Объект кэшируется по его второму запросу. Использование фильтра Блума таким образом значительно снижает нагрузку на запись на диск,поскольку одноразовые чудеса никогда не записываются в кеш диска. Кроме того, отфильтровывая одноразовые чудеса, вы также экономите место в кэше на диске, увеличивая частоту попаданий в кеш.^[11]

Как избежать ложных срабатываний в конечной вселенной [ править ]

Кисс и др. ^[28] описали новую конструкцию фильтра Блума, которая позволяет избежать ложных срабатываний в дополнение к типичному отсутствию ложноотрицательных результатов. Конструкция применима к конечной вселенной, из которой взяты элементы множества. Он основан на существующей схеме неадаптивного комбинаторного группового тестирования Эппштейна, Гудрича и Хиршберга. В отличие от типичного фильтра Блума, элементы хешируются в битовый массив с помощью детерминированных, быстрых и простых для вычисления функций. Максимальный размер набора, при котором полностью исключаются ложные срабатывания, зависит от размера юниверса и контролируется объемом выделенной памяти.

Подсчет фильтров Блума [ править ]

Счетные фильтры позволяют реализовать операцию удаления для фильтра Блума без повторного создания фильтра. В счетном фильтре позиции массива (сегменты) расширяются от одного бита до многобитового счетчика. Фактически, обычные фильтры Блума можно рассматривать как счетные фильтры с размером корзины в один бит. Счетные фильтры были введены Fan et al. (2000) .

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

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

Размер счетчиков обычно составляет 3 или 4 бита. Следовательно, подсчетные фильтры Блума занимают в 3-4 раза больше места, чем статические фильтры Блума. Напротив, структуры данных Pagh, Pagh & Rao (2005) и Fan et al. (2014) также разрешают удаление, но занимают меньше места, чем статический фильтр Блума.

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

Bonomi et al. (2006) представили структуру данных, основанную на хешировании d-left, которая функционально эквивалентна, но использует примерно половину места, чем подсчет фильтров Блума. Проблема масштабируемости не возникает в этой структуре данных. Как только проектная емкость будет превышена, ключи можно будет повторно вставить в новую хеш-таблицу двойного размера.

Вариант с эффективным использованием пространства, предложенный Putze, Sanders & Singler (2007), также может быть использован для реализации фильтров подсчета, поддерживая вставки и удаления.

Rottenstreich, Kanizo & Keslassy (2012) представили новый общий метод, основанный на переменном приращении, который значительно улучшает вероятность ложноположительных результатов подсчета фильтров Блума и их вариантов, при этом по-прежнему поддерживая удаления. В отличие от подсчета фильтров Блума, при каждой вставке элемента хешированные счетчики увеличиваются на приращение хешированной переменной вместо единичного приращения. Чтобы запросить элемент, учитываются точные значения счетчиков, а не только их положительность. Если сумма, представленная значением счетчика, не может быть составлена ​​из соответствующего приращения переменной для запрошенного элемента, на запрос может быть возвращен отрицательный ответ.

Kim et al. (2019) показывает, что количество ложных срабатываний фильтра Подсчета Блума уменьшается с k = 1 до определенной точки и увеличивается от до положительной бесконечности, и находится как функция порога подсчета. ^[29]${\displaystyle k_{opt}}$${\displaystyle k_{opt}}$${\displaystyle k_{opt}}$

Децентрализованное агрегирование [ править ]

Фильтры Блума могут быть организованы в распределенные структуры данных для выполнения полностью децентрализованных вычислений агрегатных функций . Децентрализованное агрегирование делает коллективные измерения доступными локально в каждом узле распределенной сети без привлечения для этой цели централизованного вычислительного объекта. ^[30]

Распределенные фильтры Блума [ править ]

Параллельные фильтры Блума могут быть реализованы для использования преимуществ нескольких элементов обработки (PE), присутствующих в параллельных машинах без совместного использования ресурсов . Одним из основных препятствий для параллельного фильтра Блума является организация и передача неупорядоченных данных, которые, как правило, равномерно распределяются по всем PE при запуске или при пакетной вставке. Чтобы упорядочить данные, можно использовать два подхода: либо фильтр Блума по всем данным, хранящимся на каждом PE, называемый реплицирующим фильтром Блума, либо фильтр Блума по всем данным, разделенным на равные части, причем каждый PE сохраняет одну часть. . ^[31] Для обоих подходов используется фильтр Блума «Single Shot», который вычисляет только один хэш, в результате чего на каждый элемент приходится один перевернутый бит, чтобы уменьшить объем связи.

Распределенные фильтры Блума инициируются сначала хешированием всех элементов на их локальном PE, а затем их локальной сортировкой по их хэшам. Это можно сделать за линейное время, используя, например, сортировку по сегментам, а также позволяет обнаруживать локальные дубликаты. Сортировка используется для группировки хэшей с назначенным им PE в качестве разделителя для создания фильтра Блума для каждой группы. После кодирования этих фильтров Блума с использованием, например, кодирования Голомба, каждый фильтр Блума отправляется в виде пакета на PE, ответственный за хеш-значения, которые были вставлены в него. PE p отвечает за все хэши между значениями и${\displaystyle p*(s/|{\text{PE}}|)}$${\displaystyle (p+1)*(s/|{\text{PE}}|)}$, где s - общий размер фильтра Блума по всем данным. Поскольку каждый элемент хешируется только один раз и, следовательно, устанавливается только один бит, для проверки того, был ли элемент вставлен в фильтр Блума, необходимо работать только с PE, ответственным за хеш-значение элемента. Операции одиночной вставки также могут быть выполнены эффективно, потому что фильтр Блума только для одного PE должен быть изменен, по сравнению с репликационными фильтрами Блума, где каждый PE должен обновлять свой фильтр Блума. Распределив глобальный фильтр Блума по всем PE вместо того, чтобы хранить его отдельно на каждом PE, размер фильтров Блума может быть намного больше, что приведет к большей пропускной способности и снижению частоты ложных срабатываний.
Распределенные фильтры Блума могут использоваться для улучшения алгоритмов обнаружения дубликатов ^[32]путем фильтрации самых «уникальных» элементов. Их можно вычислить, передавая только хеши элементов, а не сами элементы, которые намного больше по объему, и удаляя их из набора, уменьшая рабочую нагрузку для алгоритма обнаружения дубликатов, используемого впоследствии.

Во время передачи хэшей PE ищут биты, которые установлены более чем в одном из принимающих пакетов, так как это будет означать, что два элемента имеют одинаковый хэш и, следовательно, могут быть дубликатами. Если это происходит, сообщение, содержащее индекс бита, который также является хешем элемента, который может быть дубликатом, отправляется PE, которые отправили пакет с установленным битом. Если несколько индексов отправляются одному и тому же PE одним отправителем, может быть полезно также кодировать индексы. Все элементы, хэш которых не был отправлен обратно, теперь гарантированно не будут дублироваться и не будут оцениваться дальше, для остальных элементов используется алгоритм перераспределения ^[33]может быть использован. Сначала все элементы, хеш-значение которых было отправлено обратно, отправляются в PE, за который отвечает их хэш. Теперь любой элемент и его дубликат гарантированно находятся на одном PE. На втором этапе каждый PE использует последовательный алгоритм для обнаружения дубликатов на принимающих элементах, которые составляют лишь часть от количества начальных элементов. Допуская ложноположительный показатель для дубликатов, объем связи можно еще больше уменьшить, поскольку PE вообще не должны отправлять элементы с дублированными хэшами, и вместо этого любой элемент с дублированным хешем можно просто пометить как дубликат. В результате частота ложных срабатываний при обнаружении дубликатов такая же, как и частота ложных срабатываний используемого фильтра Блума.

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

Репликационные фильтры Блума организуют свои данные с помощью хорошо известного алгоритма гиперкуба для сплетен, например ^[34] Сначала каждый PE вычисляет фильтр Блума по всем локальным элементам и сохраняет его. Повторяя цикл, в котором на каждом шаге i PE отправляют свой локальный фильтр Блума по измерению i и объединяют фильтр Блума, который они получают по измерению, со своим локальным фильтром Блума, можно удвоить элементы, содержащиеся в каждом фильтре Блума, на каждой итерации. После отправки и получения фильтров Блума по всем измерениям каждый PE содержит глобальный фильтр Блума по всем элементам.${\displaystyle \log |{\text{PE}}|}$

Репликация фильтров Блума более эффективна, когда количество запросов намного больше, чем количество элементов, содержащихся в фильтре Блума, точка безубыточности по сравнению с распределенными фильтрами Блума находится приблизительно после обращений, при этом коэффициент ложных срабатываний фильтра Блума .${\displaystyle |{\text{PE}}|*|{\text{Elements}}|/\log _{f^{\text{+}}}|{\text{PE}}|}$${\displaystyle f^{\text{+}}}$

Синхронизация данных [ править ]

Фильтры Блума можно использовать для приблизительной синхронизации данных, как в Byers et al. (2004) . Подсчет фильтров Блума можно использовать для приблизительного определения количества различий между двумя наборами, и этот подход описан в Agarwal & Trachtenberg (2006) .

Фильтры Блумье [ править ]

Chazelle et al. (2004) разработали обобщение фильтров Блума, которые могут связывать значение с каждым вставленным элементом, реализуя ассоциативный массив . Подобно фильтрам Блума, эти структуры достигают небольших накладных расходов, принимая небольшую вероятность ложных срабатываний. В случае «фильтров Блумье» ложное срабатывание определяется как возврат результата, когда ключ отсутствует на карте. Карта никогда не вернет неправильное значение для ключа, который находится на карте.

Компактные аппроксиматоры [ править ]

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

Параллельно-секционные фильтры Блума [ править ]

В этой реализации для каждой хеш-функции использовался отдельный массив. Этот метод позволяет выполнять параллельные вычисления хешей как для вставок, так и для запросов. ^[35]

Фильтры Stable Bloom [ править ]

Deng & Rafiei (2006) предложили фильтры Стабильного Блума как вариант фильтров Блума для потоковой передачи данных. Идея состоит в том, что, поскольку нет возможности хранить всю историю потока (которая может быть бесконечной), фильтры Stable Bloom постоянно удаляют устаревшую информацию, чтобы освободить место для более новых элементов. Поскольку устаревшая информация удаляется, фильтр Stable Bloom вводит ложноотрицательные результаты, которых нет в традиционных фильтрах Bloom. Авторы показывают, что гарантирована жесткая верхняя граница частоты ложных срабатываний, и этот метод превосходит стандартные фильтры Блума с точки зрения частоты ложных срабатываний и эффективности времени, когда предоставляется небольшое пространство и приемлемая частота ложных срабатываний.

Масштабируемые фильтры Блума [ править ]

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

Фильтры Пространственного Цветения [ править ]

Фильтры пространственного Блума (SBF) были первоначально предложены Palmieri, Calderoni & Maio (2014) в качестве структуры данных, предназначенной для хранения информации о местоположении , особенно в контексте криптографических протоколов для обеспечения конфиденциальности местоположения . Однако основной характеристикой SBF является их способность хранить несколько наборов в единой структуре данных, что делает их подходящими для ряда различных сценариев приложений. ^[36] Принадлежность элемента к определенному набору может быть запрошена, и вероятность ложного срабатывания зависит от набора: первые наборы, которые должны быть введены в фильтр во время построения, имеют более высокие вероятности ложных срабатываний, чем наборы, введенные в конце. ^[37] Это свойство позволяет устанавливать приоритеты наборов, где могут быть сохранены наборы, содержащие более «важные» элементы.

Слоистые фильтры Блума [ править ]

Многослойный фильтр Блума состоит из нескольких слоев фильтра Блума. Многослойные фильтры Bloom позволяют отслеживать, сколько раз элемент был добавлен в фильтр Bloom, проверяя, сколько слоев содержит элемент. С многоуровневым фильтром Блума операция проверки обычно возвращает номер самого глубокого слоя, в котором был найден элемент. ^[38]

Аттенуированные фильтры Блума [ править ]

Ослабленный фильтр Блума глубины D можно рассматривать как массив D обычных фильтров Блума. В контексте обнаружения службы в сети каждый узел локально хранит обычные и ослабленные фильтры Блума. Обычный или локальный фильтр Блума указывает, какие услуги предлагает сам узел. Ослабленный фильтр уровня i указывает, какие службы можно найти на узлах, удаленных на i-хоп от текущего узла. I-е значение создается путем объединения локальных фильтров Блума для узлов, i-хопов, удаленных от узла. ^[39]

В качестве примера возьмем небольшую сеть, показанную на графике ниже. Скажем, мы ищем службу A, идентификатор которой хэшируется до битов 0,1 и 3 (шаблон 11010). Пусть узел n1 будет отправной точкой. Сначала мы проверяем, предлагает ли услуга A n1, проверяя ее локальный фильтр. Поскольку шаблоны не совпадают, мы проверяем ослабленный фильтр Блума, чтобы определить, какой узел должен быть следующим переходом. Мы видим, что n2 не предлагает услуги A, но находится на пути к узлам, которые ее предоставляют. Следовательно, мы переходим к n2 и повторяем ту же процедуру. Мы быстро обнаруживаем, что n3 предлагает услугу, и, следовательно, находится пункт назначения. ^[40]

Используя ослабленные фильтры Блума, состоящие из нескольких слоев, можно обнаружить услуги на расстоянии более одного скачка, избегая при этом насыщения фильтра Блума путем ослабления (смещения) битов, установленных более удаленными источниками. ^[39]

Поиск химической структуры [ править ]

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

Молекулярные отпечатки пальцев появились в конце 1940-х годов как способ поиска химических структур на перфокартах. Однако только в 1990 году компания Daylight Chemical Information Systems, Inc. представила метод на основе хешей для генерации битов вместо использования предварительно вычисленной таблицы. В отличие от словарного подхода, метод хеширования может назначать биты для подструктур, которые ранее не рассматривались. В начале 1990-х термин «отпечаток пальца» считался отличным от «структурных ключей», но с тех пор этот термин расширился, чтобы охватить большинство молекулярных характеристик, которые можно использовать для сравнения сходства, включая структурные ключи, разреженные отпечатки пальцев и трехмерные отпечатки пальцев. . В отличие от фильтров Блума, метод хеширования Daylight позволяет количеству битов, назначенных для каждой функции, зависеть от ее размера,но в большинстве реализаций отпечатков пальцев типа Daylight используется фиксированное количество бит на функцию, что делает их фильтром Блума. Исходные отпечатки пальцев Daylight можно было использовать как для проверки сходства, так и для проверки. Многие другие типы отпечатков пальцев, такие как популярный ECFP2, можно использовать для определения сходства, но не для проверки, поскольку они включают местные характеристики окружающей среды, которые при использовании в качестве экрана создают ложноотрицательные результаты. Даже если они созданы с использованием одного и того же механизма, это не фильтры Блума, потому что они не могут использоваться для фильтрации.могут использоваться для определения сходства, но не для проверки, поскольку они включают местные характеристики окружающей среды, которые при использовании в качестве экрана создают ложноотрицательные результаты. Даже если они созданы с использованием одного и того же механизма, это не фильтры Блума, потому что они не могут использоваться для фильтрации.могут использоваться для определения сходства, но не для проверки, поскольку они включают местные характеристики окружающей среды, которые при использовании в качестве экрана создают ложноотрицательные результаты. Даже если они созданы с использованием одного и того же механизма, это не фильтры Блума, потому что они не могут использоваться для фильтрации.

См. Также [ править ]

• Счетчик мин. Эскиз
• Хеширование функций
• MinHash
• Частный фильтр
• Пропустить список
• Фильтры Блума в биоинформатике
• Кукушечный фильтр

Заметки [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с фильтром Блума .

• "Использование фильтров Блума" Подробное объяснение фильтра Блума с использованием Perl
• Почему фильтры Блума работают именно так (Майкл Нильсен, 2012)
• Фильтры Блума - Учебное пособие, анализ и обзор (Blustein & El-Maazawi, 2002) в Университете Далхаузи
• Таблица количества ложных срабатываний для различных конфигураций с веб - сайта Университета Висконсина-Мэдисона
• "More Optimal Bloom Filters", Эли Порат (ноябрь 2007 г.), видео Google TechTalk на YouTube